Complete Binary Tree Node Counting and Balance Validation

Count Complete Tree Nodes (LeetCode 222)

In a complete binary tree, every level except possibly the last is completely filled, and all nodes in the last level are as far left as possible. We can exploit this to count nodes in O(log² n) time, which is significantly faster than O(n).

Logic: Depth Comparison

• Calculate the height of the leftmost path (lh) and the rightmost path (rh).
• If lh == rh: The tree is a Perfect Binary Tree. The number of nodes is exactly $2^{lh} - 1$.
• Otherwise: It is not perfect. Return $1 +$ recurse on left child $+$ recurse on right child.

public int countNodes(TreeNode root) {
    if (root == null) return 0;
    
    int lh = 0, rh = 0;
    TreeNode leftPtr = root, rightPtr = root;
    
    // Calculate leftmost depth
    while (leftPtr != null) { lh++; leftPtr = leftPtr.left; }
    // Calculate rightmost depth
    while (rightPtr != null) { rh++; rightPtr = rightPtr.right; }
    
    // If depths are equal, it's a perfect binary tree
    if (lh == rh) return (1 << lh) - 1;
    
    // Otherwise, standard recursive counting
    return 1 + countNodes(root.left) + countNodes(root.right);
}

Complexity: O(log² n). In each recursive call, height calculation takes O(log n), and there are at most O(log n) such calls because at every step, either the left or right sub-tree is guaranteed to be a perfect binary tree.

Balanced Binary Tree (LeetCode 110)

A tree is balanced if the heights of its subtrees differ by no more than 1.

Approach 1: Top-Down (O(n²))

public boolean isBalanced(TreeNode root) {
    if (root == null) return true;
    int diff = Math.abs(getHeight(root.left) - getHeight(root.right));
    return diff <= 1 && isBalanced(root.left) && isBalanced(root.right);
}

private int getHeight(TreeNode node) {
    if (node == null) return 0;
    return 1 + Math.max(getHeight(node.left), getHeight(node.right));
}

Approach 2: Bottom-Up (O(n), Recommended)

Perform post-order traversal. If any subtree is unbalanced, return -1 to trigger early termination (pruning).

public boolean isBalanced(TreeNode root) {
    return checkHeight(root) != -1;
}

private int checkHeight(TreeNode node) {
    if (node == null) return 0;
    
    int leftH = checkHeight(node.left);
    if (leftH == -1) return -1;
    
    int rightH = checkHeight(node.right);
    if (rightH == -1) return -1;
    
    if (Math.abs(leftH - rightH) > 1) return -1;
    
    return 1 + Math.max(leftH, rightH);
}

Complete Binary Tree Inserter (LeetCode 919)

A structure that supports adding new nodes to a complete binary tree while maintaining its structural properties.

class CBTInserter {
    private Deque<TreeNode> candidates = new ArrayDeque<>();
    private TreeNode root;

    public CBTInserter(TreeNode root) {
        this.root = root;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        // Collect all nodes that can still accept children
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            if (node.left == null || node.right == null) {
                candidates.offer(node);
            }
            if (node.left != null) q.offer(node.left);
            if (node.right != null) q.offer(node.right);
        }
    }

    public int insert(int val) {
        TreeNode parent = candidates.peek();
        TreeNode child = new TreeNode(val);
        candidates.offer(child);
        
        if (parent.left == null) {
            parent.left = child;
        } else {
            parent.right = child;
            // Parent is now full, remove from candidates
            candidates.poll();
        }
        return parent.val;
    }

    public TreeNode get_root() { return root; }
}

Key Takeaways