Count Complete Tree Nodes
Problem
Given the root of a complete binary tree, return the number of the nodes in the tree.
- The number of nodes in the tree is in the range [0, 5 * 10⁴]
- 0 ≤ Node.val ≤ 5 * 10⁴
- The tree is guaranteed to be complete.
Example
root = [1,2,3,4,5,6]6The tree is complete, meaning all levels except possibly the last are fully filled, and nodes in the last level are as far left as possible. The algorithm first computes the height of the leftmost path (left height) and the rightmost path (right height). If these heights are equal, the tree is perfect and the number of nodes is 2^height - 1. Otherwise, the algorithm recursively counts nodes in the left and right subtrees and sums them with 1 for the root. This approach avoids traversing every node, improving efficiency.
Approach
Straightforward Solution
A naive approach is to traverse all nodes (e.g., DFS or BFS) and count them, resulting in O(n) time complexity. This is inefficient for large trees.
Core Observation
In a complete binary tree, the leftmost path height and rightmost path height can determine if the tree is perfect (completely filled). If both heights are equal, the number of nodes is known by formula 2^height - 1 without further traversal.
Path to Optimal
The key insight is to use the properties of a complete binary tree to avoid traversing all nodes. By comparing the leftmost and rightmost heights, the algorithm can identify perfect subtrees and calculate their node counts in O(1) time. For imperfect subtrees, it recursively applies the same logic, reducing the problem size significantly.
Optimal Approach
Compute the left and right heights of the tree. If equal, return 2^height - 1. Otherwise, recursively count nodes in left and right subtrees and add 1 for the root. This approach achieves O((log n)^2) time complexity by reducing the problem size at each recursive call and avoiding full traversal.
Time
O((log n)^2)
Each recursive call computes the left and right heights in O(log n) time, and the recursion depth is O(log n) because the tree height is logarithmic in the number of nodes. Multiplying these yields O((log n)^2).
Space
O(log n)
The recursion stack depth is proportional to the height of the tree, which is O(log n) for a complete binary tree. No additional data structures are used.
Pattern Spotlight
Binary Search (Height-Based Pruning in Complete Binary Trees)
Exploit the height equality of leftmost and rightmost paths to identify perfect subtrees, enabling O(1) node count calculation and pruning large parts of the tree, thereby reducing the counting problem to a logarithmic number of recursive calls.
Solution
| 1 | class Solution: |
| 2 | def countNodes(self, root: Optional[TreeNode]) -> int: |
| 3 | if not root: |
| 4 | return 0 |
| 5 | |
| 6 | left = root |
| 7 | right = root |
| 8 | left_h = right_h = 0 |
| 9 | |
| 10 | while left: |
| 11 | left_h += 1 |
| 12 | left = left.left |
| 13 | |
| 14 | while right: |
| 15 | right_h += 1 |
| 16 | right = right.right |
| 17 | |
| 18 | if left_h == right_h: |
| 19 | return 2 ** left_h - 1 |
| 20 | |
| 21 | return 1 + self.countNodes(root.left) + self.countNodes(root.right) |
Step-by-Step Solution
Handle Empty Tree Edge Case
| 3 | if not root: |
| 4 | return 0 |
Objective
To immediately return 0 if the input tree is empty, as there are no nodes to count.
Key Insight
Checking for an empty root node is a critical base case that prevents unnecessary computation and recursion. It defines the boundary condition for the recursive counting process.
Interview Quick-Check
State & Boundaries
Return 0 immediately if the root is None, as an empty tree contains no nodes.
Compute Leftmost and Rightmost Heights to Detect Perfect Subtrees
| 6 | left = root |
| 7 | right = root |
| 8 | left_h = right_h = 0 |
| 10 | while left: |
| 11 | left_h += 1 |
| 12 | left = left.left |
| 14 | while right: |
| 15 | right_h += 1 |
| 16 | right = right.right |
Objective
To calculate the heights of the leftmost and rightmost paths from the root, which determine if the subtree is perfect.
Key Insight
In a complete binary tree, the leftmost path height and rightmost path height are easy to compute by traversing only one branch each. If these heights are equal, the subtree is perfect, allowing direct node count calculation without further recursion.
Interview Quick-Check
Core Logic
Calculating left and right heights by traversing left and right pointers respectively identifies perfect subtrees where node count can be computed in O(1).
Complexity
Each height calculation takes O(log n) time, as the height of a complete binary tree is logarithmic in the number of nodes.
Return Node Count for Perfect Subtrees Using Height Formula
| 18 | if left_h == right_h: |
| 19 | return 2 ** left_h - 1 |
Objective
To return the total number of nodes directly when the subtree is perfect, avoiding unnecessary recursion.
Key Insight
If the leftmost and rightmost heights are equal, the subtree is a perfect binary tree, and the number of nodes is exactly 2^height - 1. This formula leverages the mathematical property of perfect binary trees to optimize counting.
Interview Quick-Check
Core Logic
Using the formula 2^height - 1 for perfect subtrees eliminates the need to traverse all nodes, significantly improving efficiency.
Recursively Count Nodes in Imperfect Subtrees
| 21 | return 1 + self.countNodes(root.left) + self.countNodes(root.right) |
Objective
To recursively count nodes in the left and right subtrees when the subtree is not perfect, summing their counts with 1 for the root.
Key Insight
When the left and right heights differ, the subtree is incomplete, so the algorithm must recursively count nodes in both subtrees. Adding 1 accounts for the current root node. This divide-and-conquer approach reduces the problem size at each step.
Interview Quick-Check
Core Logic
Recursively counting nodes in left and right subtrees handles incomplete subtrees, ensuring correctness while still leveraging pruning in other parts.
Complexity
The recursion depth is O(log n), and each recursive call performs O(log n) height computations, resulting in O((log n)^2) time complexity.
Line Analysis
This solution has 4 Critical lines interviewers watch for.
return 2 ** left_h - 1Return node count for perfect subtree using formula 2^height - 1.
This formula leverages the mathematical property of perfect binary trees to compute node count in O(1) time, avoiding traversal.
if not root:Check if the root node is None (empty tree).
This base case prevents unnecessary recursion and immediately returns 0 for an empty tree, defining the termination condition for the recursion.
if left_h == right_h:Check if left and right heights are equal.
Equal heights indicate the subtree is perfect, allowing direct calculation of node count without recursion.
return 1 + self.countNodes(root.left) + self.countNodes(root.right)Recursively count nodes in left and right subtrees and add 1 for the root.
This recursive step handles incomplete subtrees by dividing the problem, ensuring correctness while still benefiting from pruning in perfect subtrees.
return 0Return 0 when the tree is empty.
Returning 0 here correctly signals that an empty tree contains no nodes, which is essential for correctness.
while left:Traverse down the leftmost path, incrementing left height.
Incrementing left height while moving left captures the depth of the leftmost branch, which is a key property of complete binary trees.
while right:Traverse down the rightmost path, incrementing right height.
Incrementing right height while moving right captures the depth of the rightmost branch, which is critical for comparison with the left height.
left_h = right_h = 0Initialize counters for left and right heights.
These counters track the number of nodes along the leftmost and rightmost paths, which determine if the subtree is perfect.
left_h += 1Increment left height counter.
Accurately counting the nodes along the leftmost path is necessary to detect perfect subtrees.
left = left.leftMove pointer to the next left child.
Progressing down the left subtree allows the algorithm to measure the full height of the leftmost path.
right_h += 1Increment right height counter.
Counting nodes along the rightmost path enables the detection of perfect subtrees by comparing with left height.
right = right.rightMove pointer to the next right child.
Progressing down the right subtree allows the algorithm to measure the full height of the rightmost path.
left = rootInitialize pointer to traverse the leftmost path.
Starting from the root, this pointer will move down the left children to compute the left height, which is critical for detecting perfect subtrees.
right = rootInitialize pointer to traverse the rightmost path.
Starting from the root, this pointer will move down the right children to compute the right height, enabling comparison with the left height.
Test Your Understanding
Why does comparing the leftmost and rightmost heights allow us to determine if a subtree is perfect and calculate its node count in O(1)?
Because in a perfect binary tree, the leftmost and rightmost heights are equal, and the number of nodes is exactly 2^height - 1. This property allows us to avoid traversing all nodes in that subtree by directly computing its size.
Related Problems
Binary Search pattern
Don't just read it. Drill it.
Reconstruct Count Complete Tree Nodes from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Count Complete Tree Nodes drill