Count Complete Tree Nodes

222.Count Complete Tree Nodes

Tree

Binary Tree

Recursion

Divide and Conquer

Problem Statement:

Given the root of a complete binary tree, return the number of nodes in the tree. Every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible.

Example:

Input:

root = [1,2,3,4,5,6]

→

Output:

6

Tree has 6 nodes total with complete filling of all levels except possibly last level

Algorithm:

1. Compare left and right height of tree
2. If equal, tree is perfect: use 2^h - 1
3. If not equal, recursively compute for subtrees
4. Handle null case separately

Complexity:

Time: O(log²n) | Space: O(1)

Java Solution:

public int countNodes(TreeNode root) {
    // Base case: empty tree
    if (root == null) return 0;
    
    // Get heights of left and right paths
    int left = leftHeight(root);
    int right = rightHeight(root);
    
    // If heights equal, tree is perfect: use 2^h - 1
    if (left == right)
        return (1 << left) - 1;
    
    // Otherwise, recursively compute for both subtrees
    return 1 + countNodes(root.right) + countNodes(root.left);
}

private int leftHeight(TreeNode node) {
    int height = 0;
    // Count nodes on leftmost path
    while (node != null) {
        node = node.left;
        height++;
    }
    return height;
}

private int rightHeight(TreeNode node) {
    int height = 0;
    // Count nodes on rightmost path
    while (node != null) {
        node = node.right;
        height++;
    }
    return height;
}

Python Solution:

def countNodes(self, root: Optional[TreeNode]) -> int:
    # Base case: empty tree
    if not root:
        return 0
        
    # Get heights of left and right paths
    left = self.leftHeight(root)
    right = self.rightHeight(root)
    
    # If heights equal, tree is perfect: use 2^h - 1
    if left == right:
        return (1 << left) - 1
        
    # Otherwise, recursively compute for both subtrees
    return 1 + self.countNodes(root.left) + self.countNodes(root.right)

def leftHeight(self, node: TreeNode) -> int:
    height = 0
    # Count nodes on leftmost path
    while node:
        node = node.left
        height += 1
    return height
    
def rightHeight(self, node: TreeNode) -> int:
    height = 0
    # Count nodes on rightmost path
    while node:
        node = node.right
        height += 1
    return height

C++ Solution:

class Solution {
public:
    int countNodes(TreeNode* root) {
        // Base case: empty tree
        if (!root) return 0;
        
        // Get heights of left and right paths
        int left = leftHeight(root);
        int right = rightHeight(root);
        
        // If heights equal, tree is perfect: use 2^h - 1
        if (left == right)
            return (1 << left) - 1;
            
        // Otherwise, recursively compute for both subtrees
        return 1 + countNodes(root->left) + countNodes(root->right);
    }
    
private:
    int leftHeight(TreeNode* node) {
        int height = 0;
        // Count nodes on leftmost path
        while (node) {
            node = node->left;
            height++;
        }
        return height;
    }
    
    int rightHeight(TreeNode* node) {
        int height = 0;
        // Count nodes on rightmost path
        while (node) {
            node = node->right;
            height++;
        }
        return height;
    }
};