Leetcode•Oct 17, 2026
Count Complete Tree Nodes
Hazrat Ali
Leetcode
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
Solution
var countNodes = function(root) {
if (!root) return 0;
let left = root;
let right = root;
let leftHeight = 0;
let rightHeight = 0;
while (left) {
leftHeight++;
left = left.left;
}
while (right) {
rightHeight++;
right = right.right;
}
if (leftHeight === rightHeight) {
return Math.pow(2, leftHeight) - 1;
}
return 1 + countNodes(root.left) + countNodes(root.right);
};