Loading…

easyTreesLC #222Sometimes asked

Count Complete Tree Nodes

Q: How do you solve Count Complete Tree Nodes using the Naive Full Traversal approach?

When to use it: Mention it as the baseline to beat — state that it's correct but O(n) and that the problem explicitly wants better. The most direct count ignores the completeness hint entirely: a tree's node count is `1` for the root plus the counts of the left and right subtrees, bottoming out at `0` for a null. This is correct for *any* binary tree. **Why it works.** Counting is a textbook fold over the tree — each node is responsible for adding itself plus delegating to its children. There is no subtlety and no edge case beyond the null base returning 0. **Why it isn't the intended answer.** It visits every one of the `n` nodes, so it is `O(n)`. The problem statement specifically asks for *less than* `O(n)`, which is a strong hint that the completeness property is meant to be exploited. Presenting this first, then saying 'but we can use the structure to do better', is exactly the progression an interviewer wants. **Why we still mention it.** It anchors correctness and gives a reference answer to sanity-check the optimized version against. On a small or arbitrary tree it's also genuinely the right call — there's no point being clever when n is tiny or the tree isn't complete. Time complexity: O(n). Space complexity: O(h).

LCPractice

Trees & BST · 16 of 41 · 11 min

Given the root of a complete binary tree, return the number of nodes in the tree.

According to Wikipedia, every level of a complete binary tree, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. The last level can hold between 1 and 2^h nodes inclusive (where h is the height of that last level).

Design an algorithm that runs in less than O(n) time complexity.

In plain English

A complete binary tree is filled top-to-bottom and, on the final level, left-to-right with no gaps. That rigid shape is the entire point of the problem: it lets us recognize 'perfect' subtrees (every level full) and count them by formula instead of visiting their nodes. We must count all nodes faster than a linear traversal would allow.

Examples

Example 1

Input: root = [1,2,3,4,5,6]
Output: 6
Note: Three full levels would be 7 nodes; the last level has 2 of its 4 possible nodes (4,5,6 fill left-to-right, so node 6 sits under 3's left), giving 6.

Example 2

Input: root = []
Output: 0
Note: An empty tree has zero nodes.

Example 3

Input: root = [1]
Output: 1
Note: Single node: left-spine height and right-spine height are both 1, so it's perfect with 2^1 − 1 = 1 node.

Constraints

The number of nodes is in the range [0, 5 × 10⁴]
0 ≤ Node.val ≤ 5 × 10⁴
The tree is guaranteed to be complete
Required: better than O(n) time

Clarifying questions4First question: What exactly does 'complete' guarantee about the shape?Explore questions

Q1.What exactly does 'complete' guarantee about the shape?
Every level except possibly the last is fully filled, and the last level fills strictly left-to-right. So there are never gaps before a node on the bottom row.
Q2.Is the explicit O(n) traversal acceptable?
It's correct but the problem explicitly asks for better than O(n). The intended answer exploits completeness to reach O(log² n).
Q3.How do you measure height — in edges or nodes?
Be consistent. Here I count nodes along the spine (an empty tree is height 0), so a perfect tree of spine height h has 2^h − 1 nodes.
Q4.Can the tree be empty?
Yes, range starts at 0. A null root returns 0 immediately.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

A naive traversal counts in O(n), but a complete tree's structure lets you do better. At each node compare the left-spine height (keep going left) with the right-spine height (keep going right). If they're equal the subtree is perfect, so it has exactly 2^height − 1 nodes — return that in O(1) without recursing. Otherwise recurse into both children. The two heights are O(log n) each and you only recurse down one genuinely-incomplete spine, giving O(log² n) total.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you go beyond the trivial O(n) count and exploit the completeness guarantee — recognizing that a perfect subtree has a closed-form size and that comparing left and right spine heights detects perfection in O(log n).

Where candidates slip

Just returning 1 + count(left) + count(right) (correct but O(n)), or mishandling the perfect-tree formula (off-by-one on 2^h vs 2^h − 1, or measuring height as edges vs nodes inconsistently).

How to stand out

Derive the O(log² n) bound out loud — O(log n) height checks at O(log n) depth — and explain WHY only one spine per level is incomplete, which is the crux of why the recursion stays logarithmic.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Naive Full Traversal	`O(n)`	`O(h)`	Mention it as the baseline to beat — state that it's correct but O(n) and that the problem explicitly wants better.	Read
2	Spine-Height Perfect-Subtree Shortcut (Optimal, O(log² n))Optimal	`O(log² n)`	`O(log n)`	The answer they want. Frame it as 'detect perfect subtrees by comparing the leftmost and rightmost depths, and count those by formula'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewAt node: L = left-spine height, R = right-spine heightL == R ?YesNoExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Naive Full Traversal

TimeO(n)SpaceO(h)

Mention it as the baseline to beat — state that it's correct but O(n) and that the problem explicitly wants better.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Forget the completeness guarantee for a moment — how would you count nodes in ANY binary tree?

2Hint 2Explore hint

Every node contributes 1. The count of a subtree is 1 plus the counts of its two children.

3Hint 3Explore hint

That's a one-line recursion, but it touches every node, so it's O(n) — the problem asks for better.

A · Core idea

The most direct count ignores the completeness hint entirely: a tree's node count is 1 for the root plus the counts of the left and right subtrees, bottoming out at 0 for a null. This is correct for any binary tree.

Why it works. Counting is a textbook fold over the tree — each node is responsible for adding itself plus delegating to its children. There is no subtlety and no edge case beyond the null base returning 0.

Why it isn't the intended answer. It visits every one of the n nodes, so it is O(n). The problem statement specifically asks for less than O(n), which is a strong hint that the completeness property is meant to be exploited. Presenting this first, then saying 'but we can use the structure to do better', is exactly the progression an interviewer wants.

Why we still mention it. It anchors correctness and gives a reference answer to sanity-check the optimized version against. On a small or arbitrary tree it's also genuinely the right call — there's no point being clever when n is tiny or the tree isn't complete.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

root = [1,2,3,4,5,6]

count(4),count(5)

each leaf → 1

Stateleaves return 1

Final result6

C · Code with teaching comments

Reference implementation preview// Definition for a binary tree node. class TreeNode { int val; TreeNode left; TreeNode right;Explore the full code

solution.javaJava

Naive Full Traversal — reference

2 teaching notes

1
// Definition for a binary tree node.
2
class TreeNode {
3
    int val;
4
    TreeNode left;
5
    TreeNode right;
6
    TreeNode(int val) { this.val = val; }
7
}
8
 
9
public int countNodes(TreeNode root) {
10
    // A null subtree has zero nodes — the base case.
11
    if (root == null) return 0;
12
    // Count this node plus everything below; correct but visits all n nodes.
13
    return 1 + countNodes(root.left) + countNodes(root.right);
14
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.14 lines

D · Why it works and complexityO(n) timeO(h) spaceOpen the invariant and proofExplore the proof

Counting is a pure structural fold: 1 + left + right. The optimized solution doesn't change what we compute, only how much of the tree we have to touch to compute it — that reframe is the whole game.

ComplexityO(n) time, O(h) space — Visits all n nodes once, O(1) work each → O(n) time. Recursion depth is the height h → O(h) stack space.

E · Edge cases and pitfalls6root = [] — Null root → 0.Explore edge cases

Edge cases handled

root = []Null root → 0.
root = [1]1 + 0 + 0 = 1.
Large complete treeCorrect answer but O(n) work — fails the 'better than O(n)' requirement.

Pitfalls

Submitting this as the final answer when the prompt demands sub-linear time.
Forgetting the null base case and dereferencing a missing child.
Counting edges instead of nodes (off-by-one).

03.2

Approach 2 of 2 · Optimal

Spine-Height Perfect-Subtree Shortcut (Optimal, O(log² n))

TimeO(log² n)SpaceO(log n)

The answer they want. Frame it as 'detect perfect subtrees by comparing the leftmost and rightmost depths, and count those by formula'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

In a complete tree, walk only left from a node to get one depth, and only right to get another. What does it mean if those two depths are equal?

2Hint 2Explore hint

Equal left and right spine heights means every level is full — the subtree is PERFECT, and a perfect tree of height h has exactly 2^h − 1 nodes. No need to count them one by one.

3Hint 3Explore hint

If the spines differ, the subtree is not perfect, so recurse into both children. Crucially, only one child's subtree is incomplete, so the recursion descends a single path — about log n levels, each doing an O(log n) height check.

A · Core idea

The completeness guarantee is not decoration — it is the lever that turns linear counting into logarithmic. The key observation: from any node, if you walk only left children you trace the left spine, and if you walk only right children you trace the right spine. In a complete tree, comparing the lengths of these two spines tells you whether the subtree is perfect (every level completely full).

Why equal spines imply a perfect subtree. Because the tree is complete, the last level fills strictly left-to-right. The left spine reaches the deepest, leftmost node; the right spine reaches the rightmost node that exists. If these two depths are equal, the bottom level must be entirely filled from left to right — there is no room for a gap, since a gap would shorten the right spine before the left. A subtree whose every level is full is perfect, and a perfect tree of spine height h (counting nodes) has exactly 2^h − 1 nodes. So when L == R we return (1 << L) - 1 in O(1) — we never touch the interior nodes at all.

Why unequal spines mean exactly one split. If L != R (specifically L > R), the subtree is not perfect, so we fall back to 1 + count(left) + count(right). This looks like it could blow up to O(n), but completeness saves us: at any node, at most one of its two children's subtrees is itself imperfect. The other is guaranteed perfect and will be answered by the formula in O(log n) on the very next call. So although we issue two recursive calls, only one of them ever recurses further — the recursion effectively walks a single root-to-bottom path.

Why the total is O(log² n). The recursion descends O(log n) levels (one path down a tree of height log n). At each level we compute two spine heights, and each spine walk is O(log n) because the tree's height is logarithmic in n. Multiplying the two logarithmic factors gives O(log² n) — dramatically better than O(n) for large trees. The space is just the O(log n) recursion depth.

Why the bit shift and the off-by-one matter. 2^h is computed as 1 << h, and we subtract 1 because a perfect tree of height h has 1 + 2 + 4 + … + 2^(h-1) = 2^h − 1 nodes. Counting the spine in nodes (empty tree height 0, single node height 1) keeps this formula clean. Mixing up edge-height and node-height is the classic source of an off-by-one here.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

root = [1,2,3,4,5,6]

Interactive diagram

Spines on [1,2,3,4,5,6]

node 1

Active call / nodeSupporting contextReturned stateNot active

Left spine 1→2→4 has height 3; right spine 1→3 has height 2 (3 has no right child) — unequal, so the root splits.

Final result6

C · Code with teaching comments

solution.javaJava

Spine-Height Perfect-Subtree Shortcut (Optimal, O(log² n)) — optimal

5 teaching notes

1
public int countNodes(TreeNode root) {
2
    if (root == null) return 0;
3
    // Depth reachable going strictly left — the deepest, leftmost node's level.
4
    int left = leftHeight(root);
5
    // Depth reachable going strictly right — the rightmost existing node's level.
6
    int right = rightHeight(root);
7
    // Equal spines ⇒ last level is fully filled ⇒ the subtree is perfect.
8
    if (left == right) {
9
        return (1 << left) - 1;            // perfect subtree → closed form
10
    }
11
    // Not perfect: split. Only one child is imperfect, so this recursion stays O(log n)
12
    // deep.
13
    return 1 + countNodes(root.left) + countNodes(root.right);
14
}
15
 
16
private int leftHeight(TreeNode node) {
17
    int h = 0;
18
    while (node != null) {                  // walk only left children
19
        h++;
20
        node = node.left;
21
    }
22
    return h;
23
}
24
 
25
private int rightHeight(TreeNode node) {
26
    int h = 0;
27
    while (node != null) {                  // walk only right children
28
        h++;
29
        node = node.right;
30
    }
31
    return h;
32
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.32 lines

D · Why it works and complexityO(log² n) timeO(log n) spaceOpen the invariant and proofExplore the proof

The completeness guarantee means imperfection lives on a single spine: at every node, one child is a perfect tree (closed-form) and only the other can be ragged. That's why two recursive calls still yield logarithmic depth — you're really binary-searching for the boundary between the full part and the empty part of the last level.

ComplexityO(log² n) time, O(log n) space — At each node we measure two spine heights, each O(log n). We recurse down at most one incomplete spine, so there are O(log n) levels of recursion. O(log n) levels × O(log n) per level = O(log² n) time. Recursion depth is O(log n) → O(log n) stack space.

E · Edge cases and pitfalls7root = [1] — leftHeight = rightHeight = 1 → perfect → (1<<1)-1 = 1.Explore edge cases

Edge cases handled

root = [1]leftHeight = rightHeight = 1 → perfect → (1<<1)-1 = 1.
Perfect tree of 7 nodesAt the root left == right == 3 → return (1<<3)-1 = 7 with zero recursion.
root = []Null root → 0 before any height check.

Pitfalls

Computing 2^h instead of 2^h − 1 (off-by-one) — a perfect tree of height h has 2^h − 1 nodes.
Mixing edge-height and node-height conventions between the two spine helpers.
Re-walking full heights at every recursive call without realizing only one branch recurses — still O(log² n), but don't panic-optimize into incorrectness.
Using 1 << left when left could exceed 31 (not an issue here given n ≤ 5×10⁴, but use long for very tall trees).

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int countNodes(TreeNode root) { if (root == null) return 0; int left = leftHeight(root); int right = rightHeight(root); if (left == right) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Off-by-one in the perfect-tree formula

A perfect tree of node-height h has 2^h − 1 nodes, not 2^h. Returning 1 << left without subtracting 1 overcounts by exactly the (nonexistent) extra bottom row.

Explore the code comparison

Don't write this

if (left == right) {
    return (1 << left);        // wrong: counts one phantom level
}

Write this instead

if (left == right) {
    return (1 << left) - 1;    // perfect tree of height h has 2^h − 1 nodes
}

Inconsistent height measurement

If leftHeight counts nodes but rightHeight counts edges, the comparison left == right is meaningless and you'll misclassify perfect subtrees. Keep both identical.

Explore the code comparison

Don't write this

def leftHeight(self, node):
    h = 0
    while node.left:        # counts edges, stops one short, and crashes on leaf? 
        h += 1
        node = node.left
    return h

def rightHeight(self, node):
    h = 0
    while node:             # counts nodes — INCONSISTENT with leftHeight
        h += 1
        node = node.right
    return h

Write this instead

def leftHeight(self, node):
    h = 0
    while node is not None:   # both count NODES
        h += 1
        node = node.left
    return h

def rightHeight(self, node):
    h = 0
    while node is not None:
        h += 1
        node = node.right
    return h

Falling back to plain O(n) recursion everywhere

Recursing 1 + count(left) + count(right) unconditionally never uses the formula, so it visits every node. The shortcut must fire whenever left == right.

Explore the code comparison

Don't write this

public int countNodes(TreeNode root) {
    if (root == null) return 0;
    return 1 + countNodes(root.left) + countNodes(root.right);  // always O(n)
}

Write this instead

public int countNodes(TreeNode root) {
    if (root == null) return 0;
    int left = leftHeight(root), right = rightHeight(root);
    if (left == right) return (1 << left) - 1;   // O(1) for perfect subtrees
    return 1 + countNodes(root.left) + countNodes(root.right);
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Perfect-subtree shortcut via left-spine vs right-spine height

Code pattern to memorize

count(node):
    if node is null: return 0
    L = leftSpineHeight(node)    # keep going .left
    R = rightSpineHeight(node)   # keep going .right
    if L == R: return (1 << L) - 1      # perfect → closed form
    return 1 + count(node.left) + count(node.right)

Rules to remember

1If left-spine height == right-spine height, the subtree is perfect → 2^h − 1 nodes, no recursion needed.
2Measure heights by walking only left and only right — that's O(h) each, not a full traversal.
3Use 1 << h (bit shift) for 2^h, then subtract 1 — but ensure h fits so the shift doesn't overflow.
4Only one child subtree per level is genuinely incomplete, so the recursion follows a single path → O(log n) deep.
5A complete tree is filled left-to-right on the last level — that property is exactly what makes the spine test valid.

Use this pattern when

Counting nodes in a guaranteed COMPLETE (or perfect) binary tree faster than O(n)
You can exploit the filled-left-to-right shape rather than visiting every node
The tree is tall and you want sub-linear work
Any problem where a perfect subtree's size has a closed form

Choose another pattern when

Tree is arbitrary / not complete → you must visit every node, O(n)
You need to process each node's value anyway → counting cheaply gains nothing
Tree is tiny → the O(n) traversal is simpler and fast enough
You need the count of leaves or a specific level, not the total

Interview takeaway

Count Complete Tree Nodes is the textbook case of exploiting structure to beat a linear scan: the completeness guarantee means most subtrees are perfect and answerable by formula. Spotting that left-spine == right-spine ⇒ perfect ⇒ 2^h − 1 turns O(n) into O(log² n).

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternExploit structural guarantees to beat a linear scan. Recognise it when a tree is promised complete/perfect: perfect subtrees have closed-form sizes, and comparing leftmost vs rightmost depth detects perfection in O(log n). The same 'measure two spines, formula or split' idea is really a binary search for the last filled position.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Maximum Depth of Binary Tree
The spine-height helpers here are exactly a depth computation along one side.
Balanced Binary Tree
Also reasons about subtree heights, but compares left vs right depth at every node for balance.
Complete Binary Tree Inserter
Coming soon
Maintains completeness under insertion — leans on the same left-to-right fill property.
Check Completeness of a Binary Tree
Coming soon
Verifies the completeness property with a BFS that forbids a node after any null.

Same pattern

←

Binary Tree Zigzag Level Order Traversal

Continue · Next problem

Flatten Binary Tree to Linked List

easyTreesLC #222Sometimes asked

Count Complete Tree Nodes

LCPractice

Trees & BST · 16 of 41 · 11 min

Given the root of a complete binary tree, return the number of nodes in the tree.

Design an algorithm that runs in less than O(n) time complexity.

In plain English

Examples

Example 1

Input: root = [1,2,3,4,5,6]
Output: 6
Note: Three full levels would be 7 nodes; the last level has 2 of its 4 possible nodes (4,5,6 fill left-to-right, so node 6 sits under 3's left), giving 6.

Example 2

Input: root = []
Output: 0
Note: An empty tree has zero nodes.

Example 3

Input: root = [1]
Output: 1
Note: Single node: left-spine height and right-spine height are both 1, so it's perfect with 2^1 − 1 = 1 node.

Constraints

The number of nodes is in the range [0, 5 × 10⁴]
0 ≤ Node.val ≤ 5 × 10⁴
The tree is guaranteed to be complete
Required: better than O(n) time

Clarifying questions4First question: What exactly does 'complete' guarantee about the shape?Explore questions

Q1.What exactly does 'complete' guarantee about the shape?
Every level except possibly the last is fully filled, and the last level fills strictly left-to-right. So there are never gaps before a node on the bottom row.
Q2.Is the explicit O(n) traversal acceptable?
It's correct but the problem explicitly asks for better than O(n). The intended answer exploits completeness to reach O(log² n).
Q3.How do you measure height — in edges or nodes?
Be consistent. Here I count nodes along the spine (an empty tree is height 0), so a perfect tree of spine height h has 2^h − 1 nodes.
Q4.Can the tree be empty?
Yes, range starts at 0. A null root returns 0 immediately.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Where candidates slip

Just returning 1 + count(left) + count(right) (correct but O(n)), or mishandling the perfect-tree formula (off-by-one on 2^h vs 2^h − 1, or measuring height as edges vs nodes inconsistently).

How to stand out

Derive the O(log² n) bound out loud — O(log n) height checks at O(log n) depth — and explain WHY only one spine per level is incomplete, which is the crux of why the recursion stays logarithmic.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Naive Full Traversal	`O(n)`	`O(h)`	Mention it as the baseline to beat — state that it's correct but O(n) and that the problem explicitly wants better.	Read
2	Spine-Height Perfect-Subtree Shortcut (Optimal, O(log² n))Optimal	`O(log² n)`	`O(log n)`	The answer they want. Frame it as 'detect perfect subtrees by comparing the leftmost and rightmost depths, and count those by formula'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Naive Full Traversal

TimeO(n)SpaceO(h)

Mention it as the baseline to beat — state that it's correct but O(n) and that the problem explicitly wants better.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Forget the completeness guarantee for a moment — how would you count nodes in ANY binary tree?

2Hint 2Explore hint

Every node contributes 1. The count of a subtree is 1 plus the counts of its two children.

3Hint 3Explore hint

That's a one-line recursion, but it touches every node, so it's O(n) — the problem asks for better.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

root = [1,2,3,4,5,6]

count(4),count(5)

each leaf → 1

Stateleaves return 1

Final result6

C · Code with teaching comments

Reference implementation preview// Definition for a binary tree node. class TreeNode { int val; TreeNode left; TreeNode right;Explore the full code

solution.javaJava

Naive Full Traversal — reference

2 teaching notes

1
// Definition for a binary tree node.
2
class TreeNode {
3
    int val;
4
    TreeNode left;
5
    TreeNode right;
6
    TreeNode(int val) { this.val = val; }
7
}
8
 
9
public int countNodes(TreeNode root) {
10
    // A null subtree has zero nodes — the base case.
11
    if (root == null) return 0;
12
    // Count this node plus everything below; correct but visits all n nodes.
13
    return 1 + countNodes(root.left) + countNodes(root.right);
14
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.14 lines

D · Why it works and complexityO(n) timeO(h) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(h) space — Visits all n nodes once, O(1) work each → O(n) time. Recursion depth is the height h → O(h) stack space.

E · Edge cases and pitfalls6root = [] — Null root → 0.Explore edge cases

Edge cases handled

root = []Null root → 0.
root = [1]1 + 0 + 0 = 1.
Large complete treeCorrect answer but O(n) work — fails the 'better than O(n)' requirement.

Pitfalls

Submitting this as the final answer when the prompt demands sub-linear time.
Forgetting the null base case and dereferencing a missing child.
Counting edges instead of nodes (off-by-one).

03.2

Approach 2 of 2 · Optimal

Spine-Height Perfect-Subtree Shortcut (Optimal, O(log² n))

TimeO(log² n)SpaceO(log n)

The answer they want. Frame it as 'detect perfect subtrees by comparing the leftmost and rightmost depths, and count those by formula'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

In a complete tree, walk only left from a node to get one depth, and only right to get another. What does it mean if those two depths are equal?

2Hint 2Explore hint

Equal left and right spine heights means every level is full — the subtree is PERFECT, and a perfect tree of height h has exactly 2^h − 1 nodes. No need to count them one by one.

3Hint 3Explore hint

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

root = [1,2,3,4,5,6]

Interactive diagram

Spines on [1,2,3,4,5,6]

node 1

Active call / nodeSupporting contextReturned stateNot active

Left spine 1→2→4 has height 3; right spine 1→3 has height 2 (3 has no right child) — unequal, so the root splits.

Final result6

C · Code with teaching comments

solution.javaJava

Spine-Height Perfect-Subtree Shortcut (Optimal, O(log² n)) — optimal

5 teaching notes

1
public int countNodes(TreeNode root) {
2
    if (root == null) return 0;
3
    // Depth reachable going strictly left — the deepest, leftmost node's level.
4
    int left = leftHeight(root);
5
    // Depth reachable going strictly right — the rightmost existing node's level.
6
    int right = rightHeight(root);
7
    // Equal spines ⇒ last level is fully filled ⇒ the subtree is perfect.
8
    if (left == right) {
9
        return (1 << left) - 1;            // perfect subtree → closed form
10
    }
11
    // Not perfect: split. Only one child is imperfect, so this recursion stays O(log n)
12
    // deep.
13
    return 1 + countNodes(root.left) + countNodes(root.right);
14
}
15
 
16
private int leftHeight(TreeNode node) {
17
    int h = 0;
18
    while (node != null) {                  // walk only left children
19
        h++;
20
        node = node.left;
21
    }
22
    return h;
23
}
24
 
25
private int rightHeight(TreeNode node) {
26
    int h = 0;
27
    while (node != null) {                  // walk only right children
28
        h++;
29
        node = node.right;
30
    }
31
    return h;
32
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.32 lines

D · Why it works and complexityO(log² n) timeO(log n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls7root = [1] — leftHeight = rightHeight = 1 → perfect → (1<<1)-1 = 1.Explore edge cases

Edge cases handled

root = [1]leftHeight = rightHeight = 1 → perfect → (1<<1)-1 = 1.
Perfect tree of 7 nodesAt the root left == right == 3 → return (1<<3)-1 = 7 with zero recursion.
root = []Null root → 0 before any height check.

Pitfalls

Computing 2^h instead of 2^h − 1 (off-by-one) — a perfect tree of height h has 2^h − 1 nodes.
Mixing edge-height and node-height conventions between the two spine helpers.
Re-walking full heights at every recursive call without realizing only one branch recurses — still O(log² n), but don't panic-optimize into incorrectness.
Using 1 << left when left could exceed 31 (not an issue here given n ≤ 5×10⁴, but use long for very tall trees).

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int countNodes(TreeNode root) { if (root == null) return 0; int left = leftHeight(root); int right = rightHeight(root); if (left == right) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Off-by-one in the perfect-tree formula

A perfect tree of node-height h has 2^h − 1 nodes, not 2^h. Returning 1 << left without subtracting 1 overcounts by exactly the (nonexistent) extra bottom row.

Explore the code comparison

Don't write this

if (left == right) {
    return (1 << left);        // wrong: counts one phantom level
}

Write this instead

if (left == right) {
    return (1 << left) - 1;    // perfect tree of height h has 2^h − 1 nodes
}

Inconsistent height measurement

If leftHeight counts nodes but rightHeight counts edges, the comparison left == right is meaningless and you'll misclassify perfect subtrees. Keep both identical.

Explore the code comparison

Don't write this

def leftHeight(self, node):
    h = 0
    while node.left:        # counts edges, stops one short, and crashes on leaf? 
        h += 1
        node = node.left
    return h

def rightHeight(self, node):
    h = 0
    while node:             # counts nodes — INCONSISTENT with leftHeight
        h += 1
        node = node.right
    return h

Write this instead

def leftHeight(self, node):
    h = 0
    while node is not None:   # both count NODES
        h += 1
        node = node.left
    return h

def rightHeight(self, node):
    h = 0
    while node is not None:
        h += 1
        node = node.right
    return h

Falling back to plain O(n) recursion everywhere

Recursing 1 + count(left) + count(right) unconditionally never uses the formula, so it visits every node. The shortcut must fire whenever left == right.

Explore the code comparison

Don't write this

public int countNodes(TreeNode root) {
    if (root == null) return 0;
    return 1 + countNodes(root.left) + countNodes(root.right);  // always O(n)
}

Write this instead

public int countNodes(TreeNode root) {
    if (root == null) return 0;
    int left = leftHeight(root), right = rightHeight(root);
    if (left == right) return (1 << left) - 1;   // O(1) for perfect subtrees
    return 1 + countNodes(root.left) + countNodes(root.right);
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Perfect-subtree shortcut via left-spine vs right-spine height

Code pattern to memorize

count(node):
    if node is null: return 0
    L = leftSpineHeight(node)    # keep going .left
    R = rightSpineHeight(node)   # keep going .right
    if L == R: return (1 << L) - 1      # perfect → closed form
    return 1 + count(node.left) + count(node.right)

Rules to remember

1If left-spine height == right-spine height, the subtree is perfect → 2^h − 1 nodes, no recursion needed.
2Measure heights by walking only left and only right — that's O(h) each, not a full traversal.
3Use 1 << h (bit shift) for 2^h, then subtract 1 — but ensure h fits so the shift doesn't overflow.
4Only one child subtree per level is genuinely incomplete, so the recursion follows a single path → O(log n) deep.
5A complete tree is filled left-to-right on the last level — that property is exactly what makes the spine test valid.

Use this pattern when

Counting nodes in a guaranteed COMPLETE (or perfect) binary tree faster than O(n)
You can exploit the filled-left-to-right shape rather than visiting every node
The tree is tall and you want sub-linear work
Any problem where a perfect subtree's size has a closed form

Choose another pattern when

Tree is arbitrary / not complete → you must visit every node, O(n)
You need to process each node's value anyway → counting cheaply gains nothing
Tree is tiny → the O(n) traversal is simpler and fast enough
You need the count of leaves or a specific level, not the total

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Maximum Depth of Binary Tree
The spine-height helpers here are exactly a depth computation along one side.
Balanced Binary Tree
Also reasons about subtree heights, but compares left vs right depth at every node for balance.
Complete Binary Tree Inserter
Coming soon
Maintains completeness under insertion — leans on the same left-to-right fill property.
Check Completeness of a Binary Tree
Coming soon
Verifies the completeness property with a BFS that forbids a node after any null.

Same pattern

←

Binary Tree Zigzag Level Order Traversal

Continue · Next problem

Flatten Binary Tree to Linked List