Check Completeness of a Binary Tree

class Solution {
public:
    int totalNodes(TreeNode* root) {
        if (!root) {
            return 0;
        }
        return 1 + totalNodes(root->left) + totalNodes(root->right);
    }

    bool validate(TreeNode* node, int position, int size) {
        if (!node) {
            return true;
        }
        if (position >= size) {
            return false;
        }
        return validate(node->left, 2 * position + 1, size) &&
               validate(node->right, 2 * position + 2, size);
    }

    bool isCompleteTree(TreeNode* root) {
        return validate(root, 0, totalNodes(root));
    }
};

The provided C++ solution checks if a binary tree is complete. A complete binary tree is one where every level, except possibly the last, is fully filled, and all nodes in the last level are as left as possible. The code consists of three main functions:

• totalNodes(TreeNode* root): This function counts the total number of nodes in the tree. It uses recursion to traverse the tree starting from the root. The base case returns 0 if the node is null, otherwise it recursively counts each subtree and adds one for the current node.

• validate(TreeNode* node, int position, int size): This function recursively checks if the tree is complete. It accepts a node and its current position as well as the size which is the total number of nodes in the tree. It verifies the condition that for a complete binary tree, no nodes exist beyond the total nodes counted. The recursion is based on validating the conditions for both left and right subtrees.

• isCompleteTree(TreeNode* root): This function is the point of entry for the process. It calls the validate function, starting at position 0 with the total number of nodes in the tree as calculated by the totalNodes function.

The process first calculates the total size of the tree and then validates whether the tree structure meets the conditions of a complete binary tree using the index properties of a 0-indexed array representation of the binary tree.

class Solution {
    public int nodeCount(TreeNode node) {
        if (node == null) {
            return 0;
        }
        return 1 + nodeCount(node.left) + nodeCount(node.right);
    }

    public boolean verifyTree(TreeNode current, int position, int totalNodes) {
        if (current == null) {
            return true;
        }
        if (position >= totalNodes) {
            return false;
        }
        return verifyTree(current.left, 2 * position + 1, totalNodes) && 
               verifyTree(current.right, 2 * position + 2, totalNodes);
    }

    public boolean isCompleteTree(TreeNode root) {
        return verifyTree(root, 0, nodeCount(root));
    }
}

This Java solution ensures the completeness of a binary tree. Completeness implies that every level, except perhaps the last, is entirely filled at all levels, and all nodes are as left as possible.

• First, the nodeCount method computes the total number of nodes by recursively visiting each node starting from the root. It returns zero for a null node, otherwise increments by one for the node itself and then recursively counts the left and right children.

• Next, the verifyTree method recursively checks nodes positioned correctly based on the zero-indexed position of the node in a hypothetical complete tree:

  • For a null node, it returns true, indicating the subtree rooted at this node is complete by default.
  • It ensures the current node's position is less than the total numbers of nodes.
  • Recursively repeats this check for the left child (at position 2 * position + 1) and right child (at position 2 * position + 2).

• Finally, the isCompleteTree method integrates these two methods. It first finds the total number of nodes using nodeCount and then uses verifyTree to determine if the tree satisfies the conditions for completeness.

This approach efficiently checks both structure and node positioning, using recursion for left and right subtree traversal, ensuring the placement of each node adheres to the required order for a complete binary tree.