Count Complete Tree Nodes
EasyPrompt
Given the root of a complete binary tree, return the number of the nodes in the tree.
According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.
Design an algorithm that runs in less than O(n) time complexity.
Example 1:
Input: root = [1,2,3,4,5,6]
Output: 6Example 2:
Input: root = []
Output: 0Example 3:
Input: root = [1]
Output: 1
Constraints:
- The number of nodes in the tree is in the range
[0, 5 * 104]. 0 <= Node.val <= 5 * 104- The tree is guaranteed to be complete.
Approaches
3 approaches with complexity analysis and trade-offs.
The most straightforward approach is to traverse the entire tree using DFS (Depth First Search) and count all nodes.
Algorithm
- If root is null, return 0
- Recursively count nodes in left subtree
- Recursively count nodes in right subtree
- Return 1 (current node) + left count + right count
Walkthrough
We can use a simple recursive DFS approach to traverse through all nodes of the tree. For each node, we add 1 to our count and recursively process the left and right children.
class Solution { public int countNodes(TreeNode root) { if (root == null) return 0; return 1 + countNodes(root.left) + countNodes(root.right); }}This solution will visit every node exactly once. While simple to implement, it doesn't take advantage of the complete binary tree property.
Complexity
Time
O(n) where n is the number of nodes in the tree
Space
O(h) where h is the height of the tree, due to recursive call stack
Trade-offs
Pros
Simple to implement
Works for any binary tree
Easy to understand
Cons
Doesn't utilize the complete binary tree property
Visits every node in the tree
Not optimal for complete binary trees
Using level order traversal (BFS) to count nodes level by level. This approach is still O(n) but provides a different way to count nodes.
Algorithm
- If root is null, return 0
- Initialize a queue with root node
- While queue is not empty:
- Poll node from queue
- Increment count
- Add left and right children to queue if they exist
- Return count
Walkthrough
We use a queue to perform level order traversal. We process nodes level by level and increment our counter for each node we encounter.
class Solution { public int countNodes(TreeNode root) { if (root == null) return 0; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int count = 0; while (!queue.isEmpty()) { TreeNode node = queue.poll(); count++; if (node.left != null) queue.offer(node.left); if (node.right != null) queue.offer(node.right); } return count; }}Complexity
Time
O(n) where n is the number of nodes in the tree
Space
O(w) where w is the maximum width of the tree
Trade-offs
Pros
Visits nodes level by level
Iterative approach (no recursion)
Good for visualizing tree structure
Cons
Still doesn't utilize complete binary tree property
Uses extra space for queue
Not optimal for complete binary trees
This optimal approach utilizes the properties of a complete binary tree to perform a binary search on the last level.
Algorithm
- If root is null, return 0
- Get height of tree by following left path
- Calculate nodes in all levels except last
- Binary search on last level:
- For each middle position, check if node exists
- Adjust search range based on existence
- Return total count
Walkthrough
We can use the fact that a complete binary tree is perfect (all levels full) except possibly for the last level. We can find the height of the tree and then binary search on the last level to find the exact number of nodes.
class Solution { public int countNodes(TreeNode root) { if (root == null) return 0; int height = getHeight(root); if (height == 0) return 1; int upperCount = (1 << height) - 1; // nodes in all levels except last int left = 0, right = (1 << height) - 1; // possible nodes in last level while (left < right) { int mid = left + (right - left + 1) / 2; if (exists(mid, height, root)) { left = mid; } else { right = mid - 1; } } return upperCount + left + 1; } private int getHeight(TreeNode root) { int height = 0; while (root.left != null) { height++; root = root.left; } return height; } private boolean exists(int idx, int height, TreeNode root) { int left = 0, right = (1 << height) - 1; for (int i = 0; i < height; i++) { int mid = left + (right - left) / 2; if (idx <= mid) { root = root.left; right = mid; } else { root = root.right; left = mid + 1; } } return root != null; }}Complexity
Time
O(log²n) where n is the number of nodes
Space
O(1) as we only use constant extra space
Trade-offs
Pros
Optimal time complexity
Takes advantage of complete binary tree properties
Doesn't visit all nodes
Cons
More complex implementation
Only works for complete binary trees
Requires understanding of binary tree properties
Solutions
Solution
/** * Definition for a binary tree node. * 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 ) { if ( root == null ) { return 0 ; } int left = depth ( root . left ); int right = depth ( root . right ); if ( left == right ) { return ( 1 << left ) + CountNodes ( root . right ); } return ( 1 << right ) + CountNodes ( root . left ); } private int depth ( TreeNode root ) { int d = 0 ; for (; root != null ; root = root . left ) { ++ d ; } return d ; } }/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public int countNodes ( TreeNode root ) { if ( root == null ) { return 0 ; } int left = depth ( root . left ); int right = depth ( root . right ); if ( left == right ) { return ( 1 << left ) + countNodes ( root . right ); } return ( 1 << right ) + countNodes ( root . left ); } private int depth ( TreeNode root ) { int d = 0 ; for (; root != null ; root = root . left ) { ++ d ; } return d ; } }/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @return {number} */ var countNodes = function (root) { const depth = (root) => { let d = 0; for (; root; root = root.left) { ++d; } return d; }; if (!root) { return 0; } const left = depth(root.left); const right = depth(root.right); if (left == right) { return (1 << left) + countNodes(root.right); } return (1 << right) + countNodes(root.left); };/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int countNodes ( TreeNode * root ) { if ( ! root ) { return 0 ; } int left = depth ( root -> left ); int right = depth ( root -> right ); if ( left == right ) { return ( 1 << left ) + countNodes ( root -> right ); } return ( 1 << right ) + countNodes ( root -> left ); } int depth ( TreeNode * root ) { int d = 0 ; for (; root ; root = root -> left ) { ++ d ; } return d ; } };# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def countNodes ( self , root : Optional [ TreeNode ]) -> int : def depth ( root ): d = 0 while root : d += 1 root = root . left return d if root is None : return 0 left , right = depth ( root . left ), depth ( root . right ) if left == right : # left child subtree: (1<<left)-1 # plus root: +1 # so total except right subtree: (1<<left) return ( 1 << left ) + self . countNodes ( root . right ) else : # left = right+1 return ( 1 << right ) + self . countNodes ( root . left ) ############ ''' >>> 2 ** 3 8 >>> 3 ** 2 9 ''' # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution ( object ): def getHeight ( self , root ): height = 0 while root : height += 1 root = root . left return height def countNodes ( self , root ): count = 0 while root : l , r = map ( self . getHeight , ( root . left , root . right )) if l == r : count += 2 ** l root = root . right else : count += 2 ** r root = root . left return countVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.