ตรวจสอบ Full Binary Tree ใน C++

โจทย์

กำหนด Binary Tree ตรวจสอบว่าเป็น Full Binary Tree หรือไม่ (ทุกโหนดมีลูก 0 หรือ 2 ตัวเท่านั้น - ไม่มีโหนดที่มีลูก 1 ตัว)

ตัวอย่าง

Full: Root มี 2 ลูก, ทุก Internal Node มี 2 ลูก, Leaf มี 0 ลูก

Not Full: มีโหนดที่มีลูกเพียง 1 ตัว (Left only หรือ Right only)

แนวคิด: Recursive Check

• Base: NULL → True (Empty tree is Full)
• Leaf (ไม่มีลูกทั้งคู่) → True
• มีลูกทั้งคู่ → Recurse ซ้ายและขวา
• มีลูกเพียงข้างเดียว → False

โค้ด C++

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

bool isFullBinaryTree(TreeNode* root) {
    if (!root) return true; // Empty tree
    
    // Leaf node
    if (!root->left && !root->right) return true;
    
    // Internal node must have BOTH children
    if (root->left && root->right) {
        return isFullBinaryTree(root->left) && isFullBinaryTree(root->right);
    }
    
    // Only one child
    return false;
}

TreeNode* createNode(int val) {
    return new TreeNode(val);
}

int main() {
    // Test 1: Full Binary Tree
    //       1
    //      / \
    //     2   3
    //    / \ / \
    //   4  5 6  7
    TreeNode* root1 = createNode(1);
    root1->left = createNode(2);
    root1->right = createNode(3);
    root1->left->left = createNode(4);
    root1->left->right = createNode(5);
    root1->right->left = createNode(6);
    root1->right->right = createNode(7);
    cout << "Test 1 (Full): " << (isFullBinaryTree(root1) ? "True" : "False") << endl;
    
    // Test 2: Not Full (Node 2 has only left child)
    //       1
    //      / \
    //     2   3
    //    /
    //   4
    TreeNode* root2 = createNode(1);
    root2->left = createNode(2);
    root2->right = createNode(3);
    root2->left->left = createNode(4);
    cout << "Test 2 (Not Full): " << (isFullBinaryTree(root2) ? "True" : "False") << endl;
    
    // Test 3: Not Full (Node 2 has only right child)
    TreeNode* root3 = createNode(1);
    root3->left = createNode(2);
    root3->right = createNode(3);
    root3->left->right = createNode(4);
    cout << "Test 3 (Not Full): " << (isFullBinaryTree(root3) ? "True" : "False") << endl;
    
    // Test 4: Single node
    TreeNode* root4 = createNode(1);
    cout << "Test 4 (Single): " << (isFullBinaryTree(root4) ? "True" : "False") << endl;
    
    // Test 5: Empty tree
    cout << "Test 5 (Empty): " << (isFullBinaryTree(nullptr) ? "True" : "False") << endl;
    
    return 0;
}

Properties ของ Full Binary Tree

• ถ้ามี n Internal Nodes → มี n + 1 Leaves
• Total Nodes = 2n + 1 (Always Odd)
• Height ≥ log₂(n+1) - 1

Complexity

• Time: O(n) - Visit every node
• Space: O(h) - Recursion stack (h = height)

Iterative Version (BFS)

bool isFullBinaryTreeBFS(TreeNode* root) {
    if (!root) return true;
    queue<TreeNode*> q;
    q.push(root);
    
    while (!q.empty()) {
        TreeNode* node = q.front(); q.pop();
        
        bool hasLeft = node->left != nullptr;
        bool hasRight = node->right != nullptr;
        
        if (hasLeft != hasRight) return false; // XOR: exactly one child
        
        if (hasLeft) q.push(node->left);
        if (hasRight) q.push(node->right);
    }
    return true;
}

ผลลัพธ์

Test 1 (Full): True
Test 2 (Not Full): False
Test 3 (Not Full): False
Test 4 (Single): True
Test 5 (Empty): True

สรุป

Full Binary Tree = ทุกโหนดมี Degree 0 หรือ 2 เท่านั้น (ไม่มี Degree 1) ตรวจสอบได้ทั้ง Recursive และ Iterative BFS - LeetCode Related: Check if Binary Tree is Full