Count Complete Tree Nodes
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.
At each node, walk the left spine and the right spine. If they have the same height h, the subtree is a perfect tree with 2^h − 1 nodes. Otherwise recurse into both children — only one side will need real work, the other returns instantly. That gives O(log² n).
level-order: [1, 2, 3, 4, 5, 6]6def count_nodes(root):
if root is None: return 0
lh, rh = 0, 0
n = root
while n: lh += 1; n = n.left
n = root
while n: rh += 1; n = n.right
if lh == rh:
return (1 << lh) - 1
return 1 + count_nodes(root.left) + count_nodes(root.right)function countNodes(root) {
if (!root) return 0;
let lh = 0, rh = 0, n = root;
while (n) { lh++; n = n.left; }
n = root;
while (n) { rh++; n = n.right; }
if (lh === rh) return (1 << lh) - 1;
return 1 + countNodes(root.left) + countNodes(root.right);
}class Solution {
public int countNodes(TreeNode root) {
if (root == null) return 0;
int lh = 0, rh = 0;
for (TreeNode n = root; n != null; n = n.left) lh++;
for (TreeNode n = root; n != null; n = n.right) rh++;
if (lh == rh) return (1 << lh) - 1;
return 1 + countNodes(root.left) + countNodes(root.right);
}
}int countNodes(TreeNode* root) {
if (!root) return 0;
int lh = 0, rh = 0;
for (auto n = root; n; n = n->left) lh++;
for (auto n = root; n; n = n->right) rh++;
if (lh == rh) return (1 << lh) - 1;
return 1 + countNodes(root->left) + countNodes(root->right);
}Explanation
We could just count every node with a plain DFS, but for a complete binary tree we can do much better by exploiting its shape. The trick is to measure the left spine and right spine heights at each node.
From the current node, walk straight down the left children to get height lh, and straight down the right children to get rh. If lh == rh, the subtree is a perfect tree, so it has exactly (1 << lh) - 1 = 2^lh - 1 nodes and we return that instantly with no further recursion.
If the spines differ, the last level is only partly filled, so we recurse: 1 + countNodes(left) + countNodes(right). Crucially, at each level only one child is imperfect — the other is perfect and answers in O(1) — so the total work is O(log² n).
Example: tree [1, 2, 3, 4, 5, 6]. At the root the left spine reaches depth 3 but the right spine only depth 2, so they differ; we recurse. The left child's subtree is perfect (height 2 → 3 nodes), the right child's left spine and right spine match shorter, and adding it all up gives 6.
By recognizing perfect subtrees with a quick spine check, we skip counting most nodes one by one.