Count Complete Tree Nodes solution and explanation
Google
9 more videos on this problem
Count Complete Tree Nodes | Leetcode #222Techdose · 13:39 · 42K views
Count Complete Tree Nodes | LeetCode 222 | C++, Java, PythonKnowledge Center · 13:57 · 8K views
Count Complete Tree Nodes (LeetCode 222) | Complete tree examples | Recursive & IterativeNikhil Lohia · 14:49 · 8K views
Leetcode - Count Complete Tree Nodes (Python)Timothy H Chang · 6:52 · 5K views
Count Complete Tree Nodes | Leetcode 222 | Live coding session 🔥🔥🔥Coding Decoded · 13:12 · 1K views
#Leetcode 222. Count Complete Tree Nodes | #JavaScriptLeetcode JavaScript · 7:49 · 713 views
Count Complete Tree Nodes | Java | LeetCode - Medium -222 | The Code MateThe Code Mate · 9:03 · 616 views
LEETCODE 222: COUNT COMPLETE TREE NODES | SOLUTION 2 WAYS | C++Nikash Kumar · 5:42 · 551 views
count complete tree nodes | count complete tree nodes leetcode | leetcode 222 | treeNaresh Gupta · 12:13 · 529 views
Leetcode 222 Count Complete Tree NodesRen Zhang · 21:56 · 164 views
The problem
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: 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 * 104]. 0 <= Node.val <= 5 * 104- The tree is guaranteed to be complete.
Approach overview
Problem Overview: Given the root of a complete binary tree, return the total number of nodes. A complete tree fills every level from left to right except possibly the last. A naive traversal works, but the structure of a complete tree allows faster counting.
Approach 1: Recursive Height Calculation (O(log² n) time, O(log n) space)
This approach uses the defining property of a complete tree. Compute the height of the leftmost path and the height of the rightmost path. If both heights are equal, the subtree is a perfect binary tree, and the node count is 2^h - 1. If the heights differ, recursively count nodes in the left and right subtrees. Each height calculation takes O(log n) and recursion happens across O(log n) levels, giving overall O(log² n) time with O(log n) recursion stack space.
This method avoids visiting every node. Instead, it repeatedly checks whether a subtree is perfect and skips full sections of the tree. It relies heavily on properties of binary trees and works well when you want a concise recursive solution.
Approach 2: Iterative Binary Search (O(log² n) time, O(1) space)
The last level of a complete tree may be partially filled. Treat the nodes on that level as indices from 0 to 2^h - 1. First compute the tree height by traversing the left edge. Then perform binary search over the index range of the last level to determine how many nodes exist. For each midpoint index, simulate the path from root to that node using bit decisions (left or right). Each existence check costs O(log n), and binary search runs O(log n) steps, producing O(log² n) total time.
This approach keeps memory constant and explicitly leverages the ordered structure of the last level. Bit decisions during traversal resemble operations discussed in bit manipulation, since each bit determines whether to move left or right while navigating the tree.
Recommended for interviews: The recursive height approach is the most common interview answer because it shows you recognize the structural property of complete trees and can reduce work by detecting perfect subtrees. The binary search method demonstrates deeper understanding of indexing the last level and is often considered the optimized conceptual solution.
Approach 1: Approach 1: Recursive Height Calculation
This approach leverages the property of a complete binary tree - where each level, except possibly the last, is completely filled and all nodes are as far left as possible. By loosely calculating the height from root to the leftmost leaf, and rightmost leaf, we can determine if the last level is fully filled and thus decide how to further count nodes efficiently.
class Solution:
def left_height(self, node):
h = 0
while node:
h += 1
node = node.left
return h
def right_height(self, node):
h = 0
while node:
h += 1
node = node.right
return h
def countNodes(self, root):
if not root:
return 0
lh = self.left_height(root)
rh = self.right_height(root)
if lh == rh:
return (1 << lh) - 1
return 1 + self.countNodes(root.left) + self.countNodes(root.right)class Solution {
private int leftHeight(TreeNode node) {
int h = 0;
while (node != null) {
h++;
node = node.left;
}
return h;
}
private int rightHeight(TreeNode node) {
int h = 0;
while (node != null) {
h++;
node = node.right;
}
return h;
}
public int countNodes(TreeNode root) {
if (root == null) {
return 0;
}
int lh = leftHeight(root);
int rh = rightHeight(root);
if (lh == rh) {
return (1 << lh) - 1;
}
return 1 + countNodes(root.left) + countNodes(root.right);
}
}#include <cmath>
int leftHeight(TreeNode* node) {
int h = 0;
while (node) {
h++;
node = node->left;
}
return h;
}
int rightHeight(TreeNode* node) {
int h = 0;
while (node) {
h++;
node = node->right;
}
return h;
}
int countNodes(TreeNode* root) {
if (!root) return 0;
int lh = leftHeight(root);
int rh = rightHeight(root);
if (lh == rh) return pow(2, lh) - 1;
return 1 + countNodes(root->left) + countNodes(root->right);
}var countNodes = function(root) {
let leftHeight = function(node) {
let h = 0;
while (node !== null) {
h++;
node = node.left;
}
return h;
};
let rightHeight = function(node) {
let h = 0;
while (node !== null) {
h++;
node = node.right;
}
return h;
};
if (!root) return 0;
let lh = leftHeight(root);
let rh = rightHeight(root);
if (lh === rh) return (1 << lh) - 1;
return 1 + countNodes(root.left) + countNodes(root.right);
};#include <math.h>
int leftHeight(struct TreeNode* node) {
int h = 0;
while (node) {
h++;
node = node->left;
}
return h;
}
int rightHeight(struct TreeNode* node) {
int h = 0;
while (node) {
h++;
node = node->right;
}
return h;
}
int countNodes(struct TreeNode* root) {
if (!root) return 0;
int lh = leftHeight(root);
int rh = rightHeight(root);
if (lh == rh) return (1 << lh) - 1;
return 1 + countNodes(root->left) + countNodes(root->right);
}public class Solution {
public int LeftHeight(TreeNode node) {
int h = 0;
while (node != null) {
h++;
node = node.left;
}
return h;
}
public int RightHeight(TreeNode node) {
int h = 0;
while (node != null) {
h++;
node = node.right;
}
return h;
}
public int CountNodes(TreeNode root) {
if (root == null) return 0;
int lh = LeftHeight(root);
int rh = RightHeight(root);
if (lh == rh) return (1 << lh) - 1;
return 1 + CountNodes(root.left) + CountNodes(root.right);
}
}This Python solution calculates the left and right height of the tree from the current node. When the heights are equal, it calculates the perfect node count using bit shifting for efficiency.
Time Complexity: O((log n)^2) since we calculate height in each recursive call.
Space Complexity: O(log n), for the recursive depth of calls.
Approach 2: Approach 2: Iterative Binary Search
The iterative approach adapts a binary search strategy on the last level of the tree, accelerated by the properties of complete trees. It minimizes node checks by directly verifying the presence of nodes via height assessment, thereby pivoting efficiently through the binary search principle.
class Solution:
def countNodes(self, root: TreeNode) -> int:
def exists(idx: int, height: int, node: TreeNode) -> bool:
left, right = 0, (1 << (height - 1)) - 1
for _ in range(height - 1):
mid = (left + right) // 2
if idx <= mid:
node = node.left
right = mid
else:
node = node.right
left = mid + 1
return node is not None
if not root:
return 0
height = self.getHeight(root)
total_nodes = (1 << (height - 1)) - 1
left, right = 1, total_nodes + 1
while left < right:
mid = (left + right) // 2
if exists(mid - 1, height, root):
left = mid + 1
else:
right = mid
return total_nodes + left
def getHeight(self, node: TreeNode) -> int:
height = 0
while node:
height += 1
node = node.left
return heightclass Solution {
public int countNodes(TreeNode root) {
if (root == null) return 0;
int height = leftHeight(root);
int left = 1, right = (1 << (height - 1)), count = right - 1;
while (left < right) {
int mid = (right + left + 1) / 2;
if (nodeExists(mid - 1, height - 1, root)) {
left = mid;
} else {
right = mid - 1;
}
}
return count + left;
}
private int leftHeight(TreeNode node) {
int h = 0;
while (node != null) {
h++;
node = node.left;
}
return h;
}
private boolean nodeExists(int idx, int height, TreeNode node) {
int left = 0, right = (1 << (height - 1)) - 1;
for (int i = 0; i < height - 1; ++i) {
int mid = (left + right) / 2;
if (idx <= mid) {
node = node.left;
right = mid;
} else {
node = node.right;
left = mid + 1;
}
}
return node != null;
}
}#include <cmath>
class Solution {
public:
int countNodes(TreeNode* root) {
if (!root) return 0;
int leftHeight(TreeNode* node) {
int h = 0;
while (node) {
h++;
node = node->left;
}
return h;
}
int height = leftHeight(root);
int start = 1, end = (1 << (height - 1));
bool nodeExists(int idx, int height, TreeNode* node) {
int left = 0, right = (1 << (height - 1)) - 1;
for (int i = 0; i < height - 1; ++i) {
int mid = (left + right) / 2;
if (idx <= mid) {
node = node->left;
right = mid;
} else {
node = node->right;
left = mid + 1;
}
}
return node != nullptr;
}
int total = (1 << (height - 1)) - 1;
while (start < end) {
int mid = (start + end + 1) / 2;
if (nodeExists(mid - 1, height - 1, root)) {
start = mid;
} else {
end = mid - 1;
}
}
return total + start;
}
};var countNodes = function(root) {
if (!root) return 0;
const leftHeight = function(node) {
let h = 0;
while (node !== null) {
h++;
node = node.left;
}
return h;
};
let height = leftHeight(root);
let start = 1, end = (1 << (height - 1));
const nodeExists = function(idx, node) {
let left = 0, right = end - 1;
for (let h = 0; h < height - 1; h++) {
let mid = (left + right) >> 1;
if (idx <= mid) {
node = node.left;
right = mid;
} else {
node = node.right;
left = mid + 1;
}
}
return node !== null;
};
let count = end - 1;
while (start < end) {
let mid = (start + end + 1) >> 1;
if (nodeExists(mid - 1, root)) {
start = mid;
} else {
end = mid - 1;
}
}
return count + start;
};#include <stdbool.h>
int countNodes(struct TreeNode* root) {
if (!root) return 0;
int leftHeight(struct TreeNode* node) {
int h = 0;
while (node) {
h++;
node = node->left;
}
return h;
}
int height = leftHeight(root);
int start = 1, end = (1 << (height - 1));
bool nodeExists(int idx, int height, struct TreeNode* node) {
int left = 0, right = (1 << (height - 1)) - 1;
while (left < right) {
int mid = (left + right) / 2;
if (idx <= mid) {
node = node->left;
right = mid;
} else {
node = node->right;
left = mid + 1;
}
}
return node != NULL;
}
int total = (1 << (height - 1)) - 1;
while (start < end) {
int mid = (start + end + 1) / 2;
if (nodeExists(mid-1, height-1, root)) {
start = mid;
} else {
end = mid - 1;
}
}
return total + start;
}public class Solution {
public int CountNodes(TreeNode root) {
if (root == null) return 0;
int height = GetHeight(root);
int left = 1, right = (1 << (height - 1)), count = right - 1;
while (left < right) {
int mid = (right + left + 1) / 2;
if (NodeExists(mid - 1, height - 1, root)) {
left = mid;
} else {
right = mid - 1;
}
}
return count + left;
}
private int GetHeight(TreeNode node) {
int height = 0;
while (node != null) {
height++;
node = node.left;
}
return height;
}
private bool NodeExists(int idx, int height, TreeNode node) {
int left = 0, right = (1 << (height - 1)) - 1;
for (int i = 0; i < height - 1; ++i) {
int mid = (left + right) / 2;
if (idx <= mid) {
node = node.left;
right = mid;
} else {
node = node.right;
left = mid + 1;
}
}
return node != null;
}
}By executing a binary search over potential nodes in the last row of a binary tree, the Python solution establishes a balance of control over tree enumeration.
Time Complexity: O((log n)^2) given repeated derivation of heights through logarithmically calculated checks.
Space Complexity: O(1).
Approach 3: Recursion
We recursively traverse the entire tree and count the number of nodes.
The time complexity is O(n), and the space complexity is O(n), where n is the number of nodes in the tree.
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func countNodes(root *TreeNode) int {
if root == nil {
return 0
}
return 1 + countNodes(root.Left) + countNodes(root.Right)
}use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
pub fn count_nodes(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
if let Some(node) = root {
let node = node.borrow();
let left = Self::depth(&node.left);
let right = Self::depth(&node.right);
if left == right {
Self::count_nodes(node.right.clone()) + (1 << left)
} else {
Self::count_nodes(node.left.clone()) + (1 << right)
}
} else {
0
}
}
fn depth(root: &Option<Rc<RefCell<TreeNode>>>) -> i32 {
if let Some(node) = root {
Self::depth(&node.borrow().left) + 1
} else {
0
}
}
}Approach 4: Binary Search
For this problem, we can also take advantage of the characteristics of a complete binary tree to design a faster algorithm.
Characteristics of a complete binary tree: leaf nodes can only appear on the bottom and second-to-bottom layers, and the leaf nodes on the bottom layer are concentrated on the left side of the tree. It should be noted that a full binary tree is definitely a complete binary tree, but a complete binary tree is not necessarily a full binary tree.
If the number of layers in a full binary tree is h, then the total number of nodes is 2^h - 1.
We first count the heights of the left and right subtrees of root, denoted as left and right.
- If
left = right, it means that the left subtree is a full binary tree, so the total number of nodes in the left subtree is2^{left} - 1. Plus therootnode, it is2^{left}. Then we recursively count the right subtree. - If
left > right, it means that the right subtree is a full binary tree, so the total number of nodes in the right subtree is2^{right} - 1. Plus therootnode, it is2^{right}. Then we recursively count the left subtree.
The time complexity is O(log^2 n).
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func countNodes(root *TreeNode) int {
if root == nil {
return 0
}
left, right := depth(root.Left), depth(root.Right)
if left == right {
return (1 << left) + countNodes(root.Right)
}
return (1 << right) + countNodes(root.Left)
}
func depth(root *TreeNode) (d int) {
for ; root != nil; root = root.Left {
d++
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Recursive Height Calculation | Time Complexity: |
| Approach 2: Iterative Binary Search | Time Complexity: |
| Recursion | – |
| Binary Search | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Height Calculation | O(log² n) | O(log n) | Best general approach for interviews; easy to implement using recursion and subtree height checks. |
| Iterative Binary Search on Last Level | O(log² n) | O(1) | Useful when constant extra space is preferred and you want to explicitly exploit the last-level indexing of a complete tree. |
Frequently asked questions
Is Count Complete Tree Nodes easy or hard?
The problem is labeled Easy on LeetCode because the core idea is recognizing the structure of a complete binary tree. However, discovering the O(log² n) optimization instead of a full traversal can feel closer to a medium-level insight for many candidates.
Count Complete Tree Nodes Python/Java solution
Both Python and Java implementations typically compute subtree heights and apply recursion. The logic checks whether left and right heights are equal to determine if a subtree is perfect. If so, return 2^h - 1; otherwise recursively count nodes in both children.
How to solve Count Complete Tree Nodes in O(n)?
Traverse the tree using DFS or BFS and increment a counter for each visited node. This guarantees correctness for any binary tree and runs in O(n) time with O(h) recursion stack or O(n) queue space depending on the traversal method. It ignores the complete-tree optimization.
What is the best approach for Count Complete Tree Nodes?
The most common solution uses recursive height comparison. Compute the height of the leftmost and rightmost paths. If they match, the subtree is perfect and contains 2^h - 1 nodes. Otherwise recurse on the children. This runs in O(log² n) time because height computation and recursion both take O(log n).
Is Count Complete Tree Nodes asked at Google/Amazon/Meta?
Count Complete Tree Nodes frequently appears in interviews at large tech companies because it tests recognition of structural properties in trees. Instead of brute-force traversal, candidates are expected to detect perfect subtrees or apply binary search on the last level.
What data structure is used in Count Complete Tree Nodes?
The problem uses a binary tree, specifically a complete binary tree. Efficient solutions rely on properties of complete trees, such as predictable height and contiguous node placement on each level, combined with binary search or subtree height calculations.
What is the time complexity of Count Complete Tree Nodes?
The optimized solutions run in O(log² n) time. Each step computes subtree height or performs a node-existence check in O(log n), and the process repeats across O(log n) levels. A simple DFS or BFS traversal would take O(n) time instead.