🧠
Optimal (Iterative Binary Search on Last Level)
💡 This approach uses binary search on the last level to count nodes without recursion, further optimizing performance and avoiding stack overhead.
Intuition
Since the tree is complete, the last level nodes are filled from left to right. We can binary search the index of the last node on the last level by checking node existence.
Algorithm
- Compute tree height by traversing left children.
- If height is 0, return 0.
- Use binary search on the range [0, 2^(height-1) - 1] to find the last existing node index on the last level.
- Check node existence by traversing from root using bits of the index.
- Return total nodes as nodes above last level plus last level count.
💡 This approach avoids recursion and uses binary search to minimize node visits.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def height(root):
h = 0
while root:
h += 1
root = root.left
return h
def exists(idx, h, root):
left, right = 0, 2**(h - 1) - 1
for _ in range(h - 1):
mid = (left + right) // 2
if idx <= mid:
root = root.left
right = mid
else:
root = root.right
left = mid + 1
return root is not None
def countNodes(root):
if not root:
return 0
h = height(root)
if h == 1:
return 1
left, right = 0, 2**(h - 1) - 1
while left <= right:
mid = (left + right) // 2
if exists(mid, h, root):
left = mid + 1
else:
right = mid - 1
return (2**(h - 1) - 1) + left
# Example usage:
if __name__ == '__main__':
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, TreeNode(6), None))
print(countNodes(root)) # Output: 6
Line Notes
def height(root):Compute tree height by going left
while root:Traverse left children to measure height
def exists(idx, h, root):Check if node at index idx exists on last level
for _ in range(h - 1):Traverse tree according to bits of idx to decide path
if idx <= mid:If idx is in left half, go left subtree and update right boundary
else:If node does not exist, search left half
return root is not NoneReturn True if node exists at this path, else False
while left <= right:Binary search over last level indices to find last existing node
if exists(mid, h, root):If node exists at mid, search right half to find last node
return (2**(h - 1) - 1) + leftReturn total nodes: full levels plus count of last level nodes
public class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
private int height(TreeNode root) {
int h = 0;
while (root != null) {
h++;
root = root.left;
}
return h;
}
private boolean exists(int idx, int h, TreeNode root) {
int left = 0, right = (1 << (h - 1)) - 1;
for (int i = 0; i < h - 1; i++) {
int mid = (left + right) / 2;
if (idx <= mid) {
root = root.left;
right = mid;
} else {
root = root.right;
left = mid + 1;
}
}
return root != null;
}
public int countNodes(TreeNode root) {
if (root == null) return 0;
int h = height(root);
if (h == 1) return 1;
int left = 0, right = (1 << (h - 1)) - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (exists(mid, h, root)) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return (1 << (h - 1)) - 1 + left;
}
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.left = new TreeNode(6);
Solution sol = new Solution();
System.out.println(sol.countNodes(root)); // Output: 6
}
}
Line Notes
private int height(TreeNode root)Compute tree height by traversing left children
while (root != null)Loop down left subtree to measure height
private boolean exists(int idx, int h, TreeNode root)Check if node exists at index idx on last level
for (int i = 0; i < h - 1; i++)Traverse tree according to bits of idx to decide path
if (idx <= mid)If idx in left half, go left subtree and update right boundary
elseIf node does not exist, search left half
return root != null;Return true if node exists at this path
while (left <= right)Binary search over last level indices to find last existing node
if (exists(mid, h, root))If node exists at mid, search right half
return (1 << (h - 1)) - 1 + left;Return total nodes: full levels plus last level count
#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
int height(TreeNode* root) {
int h = 0;
while (root) {
h++;
root = root->left;
}
return h;
}
bool exists(int idx, int h, TreeNode* root) {
int left = 0, right = (1 << (h - 1)) - 1;
for (int i = 0; i < h - 1; i++) {
int mid = (left + right) / 2;
if (idx <= mid) {
root = root->left;
right = mid;
} else {
root = root->right;
left = mid + 1;
}
}
return root != nullptr;
}
int countNodes(TreeNode* root) {
if (!root) return 0;
int h = height(root);
if (h == 1) return 1;
int left = 0, right = (1 << (h - 1)) - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (exists(mid, h, root)) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return (1 << (h - 1)) - 1 + left;
}
int main() {
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
root->right->left = new TreeNode(6);
cout << countNodes(root) << endl; // Output: 6
return 0;
}
Line Notes
int height(TreeNode* root)Compute tree height by traversing left children
while (root)Loop down left subtree to measure height
bool exists(int idx, int h, TreeNode* root)Check if node exists at index idx on last level
for (int i = 0; i < h - 1; i++)Traverse tree according to bits of idx to decide path
if (idx <= mid)If idx in left half, go left subtree and update right boundary
elseIf node does not exist, search left half
return root != nullptr;Return true if node exists at this path
while (left <= right)Binary search over last level indices to find last existing node
if (exists(mid, h, root))If node exists at mid, search right half
return (1 << (h - 1)) - 1 + left;Return total nodes: full levels plus last level count
function TreeNode(val, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
function height(root) {
let h = 0;
while (root) {
h++;
root = root.left;
}
return h;
}
function exists(idx, h, root) {
let left = 0, right = (1 << (h - 1)) - 1;
for (let i = 0; i < h - 1; i++) {
let mid = Math.floor((left + right) / 2);
if (idx <= mid) {
root = root.left;
right = mid;
} else {
root = root.right;
left = mid + 1;
}
}
return root !== null;
}
function countNodes(root) {
if (root === null) return 0;
const h = height(root);
if (h === 1) return 1;
let left = 0, right = (1 << (h - 1)) - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (exists(mid, h, root)) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return (1 << (h - 1)) - 1 + left;
}
// Example usage:
const root = new TreeNode(1,
new TreeNode(2, new TreeNode(4), new TreeNode(5)),
new TreeNode(3, new TreeNode(6), null)
);
console.log(countNodes(root)); // Output: 6
Line Notes
function height(root)Compute tree height by traversing left children
while (root)Loop down left subtree to measure height
function exists(idx, h, root)Check if node exists at index idx on last level
for (let i = 0; i < h - 1; i++)Traverse tree according to bits of idx to decide path
if (idx <= mid)If idx in left half, go left subtree and update right boundary
elseIf node does not exist, search left half
return root !== null;Return true if node exists at this path
while (left <= right)Binary search over last level indices to find last existing node
if (exists(mid, h, root))If node exists at mid, search right half
return (1 << (h - 1)) - 1 + left;Return total nodes: full levels plus last level count
TimeO((log n)^2)
SpaceO(1)
Binary search on last level indices takes O(log n), each existence check takes O(log n), total O((log n)^2).
💡 For n=100,000 nodes, this means about 289 operations, very efficient and avoids recursion stack overhead.
Interview Verdict: Accepted and optimal iterative solution
This approach is the most efficient and avoids recursion, ideal for interviews if comfortable with binary search on trees.