DSA · Trees · #60

Count Complete Tree Nodes

Module 44 · difficulty 3/5·⏱ 30:00starts on first keystroke

Given the `root` of a **complete binary tree**, return the number of nodes in the tree. A complete binary tree is one in which every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between `1` and `2^h` nodes inclusive at the last level `h`. Implement `countNodes(root)` where each tree node is `{ val, left, right }` (with `left`/`right` being `null` when absent). The challenge is to do better than the trivial `O(n)` traversal.

Examples

root = [1,2,3,4,5,6] → 6 — Level order; the last level (4,5,6) is filled left to right.
root = [] → 0 — An empty tree has zero nodes.
root = [1] → 1

Constraints

· The number of nodes is in the range [0, 5 * 10^4].
· 0 <= Node.val <= 5 * 10^4
· The tree is guaranteed to be complete.
· Aim for better than O(n): the intended solution runs in O(log^2 n).

Session phases

A · Clarify

B · Approach

C · Complexity

D · Edges

E · Code

F · Tradeoff

G · Score

Phase A — Clarify

Ask questions about input bounds, types, and edge constraints.

Ask the coach clarifying questions about the problem.

When you've covered this phase, advance to the next.