Solution Explanation for Counting Complete Tree Nodes

This problem asks us to count the number of nodes in a complete binary tree. A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

We'll explore two solutions: a straightforward recursive approach and a more optimized binary search-based solution that leverages the properties of a complete binary tree.

Solution 1: Recursive Approach (Time Complexity: O(n))

This is the simplest approach. We recursively traverse the tree, counting each node encountered. The base case is an empty tree (null node), which returns 0. Otherwise, we count the root (1) and recursively count the nodes in the left and right subtrees.

Time Complexity: O(n), where n is the number of nodes in the tree. We visit each node exactly once.

Space Complexity: O(h), where h is the height of the tree. This is due to the recursive call stack. In the worst case (a skewed tree), h could be n, but for a complete binary tree, h is generally log₂(n).

Solution 2: Binary Search Approach (Time Complexity: O(log₂n)²)

This approach is significantly faster for complete binary trees. It exploits the properties of a complete binary tree to avoid visiting every node.

The core idea is to find the height of the left and right subtrees. Since the tree is complete, one subtree will always be a full binary tree (meaning it has 2h -1 nodes, where h is its height). We use this fact to calculate the number of nodes in the full subtree directly (without recursion). Then we recursively count the nodes in the other subtree (which might not be full).

Time Complexity: O(log₂n)² . We compute the depth of the left and right subtrees in O(log n) time each, and we do this for each recursive call. The recursion depth is also logarithmic.

Space Complexity: O(log n). The recursive call stack depth is proportional to the height of the tree, which is logarithmic for a complete binary tree.

Code Examples (Multiple Languages)

The code examples below demonstrate both solutions in various programming languages. Note that the recursive approach is generally simpler to implement, while the binary search method provides significantly better performance for larger complete binary trees.

(Note: The following code snippets assume a standard TreeNode definition is available in each language. These definitions are omitted for brevity.)

Python

# Solution 1: Recursive
def countNodes_recursive(root):
    if root is None:
        return 0
    return 1 + countNodes_recursive(root.left) + countNodes_recursive(root.right)
 
 
# Solution 2: Binary Search
def countNodes_binary_search(root):
    def depth(node):
        d = 0
        while node:
            d += 1
            node = node.left
        return d
 
    if root is None:
        return 0
    left_depth, right_depth = depth(root.left), depth(root.right)
    if left_depth == right_depth:
        return (1 << left_depth) + countNodes_binary_search(root.right)
    return (1 << right_depth) + countNodes_binary_search(root.left)

Java

// Solution 1: Recursive
public int countNodesRecursive(TreeNode root) {
    if (root == null) return 0;
    return 1 + countNodesRecursive(root.left) + countNodesRecursive(root.right);
}
 
// Solution 2: Binary Search
public int countNodesBinarySearch(TreeNode root) {
    int leftDepth = getDepth(root.left);
    int rightDepth = getDepth(root.right);
    if (leftDepth == rightDepth) {
        return (1 << leftDepth) + countNodesBinarySearch(root.right);
    }
    return (1 << rightDepth) + countNodesBinarySearch(root.left);
}
 
private int getDepth(TreeNode node) {
    int depth = 0;
    while (node != null) {
        depth++;
        node = node.left;
    }
    return depth;
}

C++

// Solution 1: Recursive
int countNodesRecursive(TreeNode* root) {
    if (root == nullptr) return 0;
    return 1 + countNodesRecursive(root->left) + countNodesRecursive(root->right);
}
 
 
// Solution 2: Binary Search
int countNodesBinarySearch(TreeNode* root) {
    int leftDepth = getDepth(root->left);
    int rightDepth = getDepth(root->right);
    if (leftDepth == rightDepth) {
        return (1 << leftDepth) + countNodesBinarySearch(root->right);
    }
    return (1 << rightDepth) + countNodesBinarySearch(root->left);
}
 
int getDepth(TreeNode* node) {
    int depth = 0;
    while (node != nullptr) {
        depth++;
        node = node->left;
    }
    return depth;
}

(Similar code can be written for other languages like JavaScript, Go, Rust, etc., following the same logic.)

This detailed explanation and code examples should help you understand both approaches to solving the "Count Complete Tree Nodes" problem. Remember to choose the solution that best suits your needs based on the size of the input tree and performance requirements. For very large complete binary trees, the binary search approach offers a significant advantage in efficiency.