Count Complete Tree Nodes
Easy · Binary Search · Explanation and code example
Recognize Perfect Complete Subtrees
How it works
In a complete tree, equal depths along the far-left and far-right paths identify a perfect subtree. Its node count is 2^height - 1. When the depths differ, recursively count the children; at each level one child is perfect and can be counted directly.
Steps
- Measure the far-left and far-right depths.
- If equal, return 2^height - 1.
- Otherwise return one plus both child counts.
Complexity
- Time: O(log² n), relying on completeness.
- Space: O(log n) recursion stack.
Things to watch for
- The input must be a complete tree.
- The measured height includes the root.
- The same shortcut is not valid for an arbitrary sparse binary tree.
Python code example
class Solution:
def countNodes(self, root: TreeNode | None) -> int:
if not root:
return 0
left = root
right = root
heightL = 0
heightR = 0
while left:
heightL += 1
left = left.left
while right:
heightR += 1
right = right.right
if heightL == heightR: # `root` is a complete tree.
return pow(2, heightL) - 1
return 1 + self.countNodes(root.left) + self.countNodes(root.right)
C++ code example
class Solution {
public:
int countNodes(TreeNode* root) {
if (root == nullptr)
return 0;
TreeNode* left = root;
TreeNode* right = root;
int heightL = 0;
int heightR = 0;
while (left != nullptr) {
++heightL;
left = left->left;
}
while (right != nullptr) {
++heightR;
right = right->right;
}
if (heightL == heightR) // `root` is a complete tree.
return pow(2, heightL) - 1;
return 1 + countNodes(root->left) + countNodes(root->right);
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.