Count Nodes in a Complete Binary Tree
Problem
A complete binary tree has every level fully filled except possibly the last, which is filled left-to-right. Count its nodes faster than O(n).
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).
Input
level-order: [1, 2, 3, 4, 5, 6]Output
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);
}