DSA interview question

Count Nodes in a Complete Binary Tree

Easy · Data structures · Topics: tree, binary search

The problem

A heap-backed job queue stores tasks in a complete binary tree: every level is full except possibly the last, which is filled from the left. The monitoring dashboard wants the node count faster than visiting every node. The shape makes that possible. If the leftmost path and the rightmost path from a node have the same length h, the subtree is perfect and has exactly 2^h − 1 nodes. Otherwise, count the two children recursively. At most one child at each level is not perfect, so the recursion follows a single path: O(log² n).

Example: [1, 2, 3, 4, 5, 6] → 6.

Function signature

int countNodes(TreeNode* root);  // root of a complete binary tree

Test cases

Input (level order)	Output	Explanation
`[1, 2, 3, 4, 5, 6]`	`6`	The last level is partly filled
`[1, 2, 3, 4, 5, 6, 7]`	`7`	Perfect: 2³ − 1
`[1, 2, 3, 4]`	`4`
`[1]`	`1`
`[]`	`0`

(Confirm: the tree is complete; the goal is better than O(n).)

How interviewers phrase it

"Given the root of a complete binary tree, return the number of nodes, in less than O(n) time" (LeetCode 222).

Clarifying questions to ask

Is the tree guaranteed complete? (Yes, and the speed-up depends on it.)
Is O(n) acceptable? (It's correct but misses the point.)
How many nodes? (Up to 5·10⁴.)

Follow-ups to expect

"Why does equal left and right height mean perfect?"
"Why only O(log² n)?"
"Binary-search alternative?"
"Why use 1 << h?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview