222. Count Complete Tree Nodes

Tree Depth-First Search Binary Search Binary Tree

Time: O(log^2 n)

Space: O(log n)

Intuition

In a complete binary tree, count the height by going all-left and all-right. If they're equal, the left subtree is a perfect tree of height h-1 (so 2^(h-1)-1 nodes) plus root = 2^h-1 ... or use binary search on the last-level nodes in O(log^2n).

Algorithm

1Compute leftH (go left) and rightH (go right) from root.
2If leftH == rightH: full tree -> return (1 << leftH) - 1.
3Else: return CountNodes(root.left) + CountNodes(root.right) + 1.

Example Walkthrough

Input: Complete tree with 6 nodes

1.Root: leftH=3, rightH=2 -> not full. Recurse.
2.Root.left: leftH=2, rightH=2 -> full subtree, 3 nodes.
3.Root.right: leftH=1, rightH=1 -> full subtree, 1 node.
4.Total = 3+1+1 = 5... (depends on actual tree structure).

Output: 6

Common Pitfalls

•Only O(log^2n) recursion depth - not O(n). The leftH==rightH check prunes half the tree each time.

222.cs

// Approach: Exploit the complete binary tree property to count faster than O(n).
// Compute left-height (leftmost path) hl and right-height (rightmost path) hr.
// If hl == hr, the left subtree is a perfect binary tree with 2^hl - 1 nodes; recurse only on the right.
// If hl != hr, the right subtree is perfect with 2^hr - 1 nodes; recurse only on the left.
// Each recursive call eliminates exactly half the tree, giving O(log n) levels of recursion.
// Each level computes two heights in O(log n) time, so the total is O(log^2 n).
// Time: O(log^2 n) Space: O(log n) for the recursion stack.

public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
    {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution
{
    public int CountNodes(TreeNode root)
    {
        //return PreOrderCount(root);
        //return PostOrderCount(root);
        return InOrderCount(root);
    }

    private int PreOrderCount(TreeNode root)
    {
        if (root == null)
            return 0;

        int ans = 0;
        ans += 1;
        ans += PreOrderCount(root.left);
        ans += PreOrderCount(root.right);
        return ans;
    }

    private int PostOrderCount(TreeNode root)
    {
        if (root == null)
            return 0;

        int ans = 0;
        ans += PostOrderCount(root.left);
        ans += PostOrderCount(root.right);
        ans += 1;
        return ans;
    }

    private int InOrderCount(TreeNode root)
    {
        if (root == null)
            return 0;

        int ans = 0;
        ans += InOrderCount(root.left);
        ans += 1;
        ans += InOrderCount(root.right);
        return ans;
    }
}

Was this solution helpful?