Count Complete Tree Nodes

Count Complete Tree Nodes

What is this problem about?

The Count Complete Tree Nodes interview question asks you to find the total number of nodes in a "complete" binary tree. In a complete tree, every level is filled except possibly the last, which is filled from left to right. While you could count nodes by traversing the whole tree (O(N)), the goal here is to do it in less than O(N) time by leveraging the tree's structure.

Why is this asked in interviews?

Companies like Apple, Meta, and Google use the Binary Search interview pattern for this problem to test your knowledge of tree properties. It evaluates whether you can use a binary search approach on a tree, which is a "Medium" difficulty task. It demonstrates your ability to optimize an O(N) problem into O((log N)^2).

Algorithmic pattern used

The problem uses Binary Search on the Leaves.

1. Calculate the height h of the tree by going left from the root.
2. The total nodes in a perfect tree of height h is 2^h - 1.
3. The actual count is (nodes in top h-1 levels) + (nodes in the last level).
4. Use binary search to find how many nodes exist in the last level. To check if the $i^{th}$ node exists at depth h, you can use the binary representation of i to guide your path from the root.

Example explanation

Height h=2 (Root at depth 0).

1. Top levels (0 and 1) have 2^2 - 1 = 3 nodes.
2. Last level (depth 2) can have up to 2^2 = 4 nodes.
3. Binary search for the number of leaves in [0, 3].
4. To check leaf 2 (binary 10): Start at root, go Right (1), then Left (0).
5. If that node exists, we know there are at least 3 leaves.

Common mistakes candidates make

• Linear Traversal: Returning a standard DFS/BFS count, which is O(N). Interviewers usually expect the O(log^2 N) solution.
• Height Calculation: Confusing "height" (edges) with "depth" (nodes).
• Binary Path logic: Implementing the "check if node exists" function incorrectly.

Interview preparation tip

Always remember the property of complete trees in an array: the child of i is 2i+1 and 2i+2. While you don't use an array here, the same binary logic applies to finding the path to a specific leaf.