Count Complete Tree Nodes

Difficulty: Easy | Acceptance: 72.50% | Paid: No Topics: Binary Search, Bit Manipulation, Tree, Binary Tree

Given the root of a complete binary tree, return the number of nodes in the tree.

A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible.

Design an algorithm that runs in less than O(n) time complexity.

• Examples
• Constraints
• Brute Force (DFS)
• Binary Search on Last Level
• Recursive Divide and Conquer

Examples

Example 1:

Input: root = [1,2,3,4,5,6]
Output: 6

Example 2:

Input: root = []
Output: 0

Example 3:

Input: root = [1]
Output: 1

Constraints

The number of nodes in the tree is in the range [0, 5 * 10^4].
0 <= Node.val <= 5 * 10^4
The tree is guaranteed to be a complete binary tree.

Brute Force (DFS)

Intuition The simplest way to count nodes is to traverse the entire tree using Depth First Search (DFS), visiting every node exactly once and incrementing a counter.

Steps

• If the root is null, return 0.
• Recursively count nodes in the left subtree.
• Recursively count nodes in the right subtree.
• Return the sum of left count, right count, and 1 (for the current node).

class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        return 1 + self.countNodes(root.left) + self.countNodes(root.right)

Complexity

• Time: O(N) where N is the number of nodes.
• Space: O(H) where H is the height of the tree, for the recursion stack.
• Notes: This approach visits every node, which is inefficient for large complete trees.

Binary Search on Last Level

Intuition In a complete binary tree, all levels except the last are fully filled. The last level is filled from left to right. We can calculate the number of nodes in the upper levels (2ʰ - 1) and use binary search to determine how many nodes exist in the last level.

Steps

• Calculate the depth d of the tree (the number of edges from root to the deepest leaf).
• If depth is 0, return 1.
• The number of nodes in the last level can range from 1 to 2ᵈ. Perform a binary search on the index of the last node (0 to 2ᵈ - 1).
• For each midpoint index, check if a node exists at that position in the last level by traversing the path determined by the binary representation of the index.
• If the node exists, search the right half; otherwise, search the left half.
• The total nodes is the sum of nodes in upper levels and the count found in the last level.

class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        
        def depth(node):
            d = 0
            while node.left:
                node = node.left
                d += 1
            return d
        
        d = depth(root)
        
        if d == 0:
            return 1
        
        def exists(idx, d, node):
            left, right = 0, 2**d - 1
            for _ in range(d):
                mid = (left + right) // 2
                if idx <= mid:
                    node = node.left
                    right = mid
                else:
                    node = node.right
                    left = mid + 1
            return node is not None
        
        left, right = 0, 2**d - 1
        while left <= right:
            mid = (left + right) // 2
            if exists(mid, d, root):
                left = mid + 1
            else:
                right = mid - 1
        
        return (2**d - 1) + left

Complexity

• Time: O(log² N) - We perform binary search (O(log N)) and for each check, we traverse the height of the tree (O(log N)).
• Space: O(1) - Iterative approach uses constant space.
• Notes: Efficiently handles the constraint of not visiting all nodes.

Recursive Divide and Conquer

Intuition We can leverage the property of complete binary trees recursively. If the left and right subtrees of a node have the same height, the left subtree is a perfect binary tree. If they differ, the right subtree is a perfect binary tree. We can calculate the nodes in a perfect tree instantly using 2ʰ - 1.

Steps

• Define a helper function to compute the height of a tree by going only to the left.
• Compare the height of the left and right subtrees of the current root.
• If heights are equal, the left subtree is perfect. Total nodes = nodes in left perfect tree + 1 (root) + nodes in right subtree.
• If heights are not equal, the right subtree is perfect. Total nodes = nodes in right perfect tree + 1 (root) + nodes in left subtree.
• Recurse until the base case (null node).

class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        
        left_depth = self.get_depth(root.left)
        right_depth = self.get_depth(root.right)
        
        if left_depth == right_depth:
            return (1 << left_depth) + self.countNodes(root.right)
        else:
            return (1 << right_depth) + self.countNodes(root.left)
    
    def get_depth(self, node):
        depth = 0
        while node:
            node = node.left
            depth += 1
        return depth

Complexity

• Time: O(log² N) - We visit O(log N) nodes, and for each node, we calculate depth which takes O(log N).
• Space: O(log N) - Recursion stack depth is proportional to the height of the tree.
• Notes: This is a clean recursive solution that optimizes by skipping perfect subtrees.