202. Count Complete Tree Nodes
You are handed the root of a binary tree that is guaranteed to be complete: every level is entirely filled except possibly the deepest one, and the nodes on that deepest level are packed as far left as they can go. Each node exposes val, left, and right (a missing child is None/null). Return the total number of nodes in the tree.
Any traversal counts the nodes in O(n) — the interesting part is that the completeness guarantee lets you finish in O(log² n) without ever visiting most of the tree. Aim for that.
Example 1:
Input: root = [1, 2, 3, 4, 5, 6]
Output: 6
Explanation: The first two levels are full (1 + 2 nodes) and the last level holds 3 of its 4 possible slots, filled from the left — 6 nodes total.
Example 2:
Input: root = [1]
Output: 1
Explanation: A single root is a complete tree of one node.
Constraints:
- 1 ≤ number of nodes ≤ 10⁴
- 0 ≤ node value ≤ 5 * 10⁴
- The tree is guaranteed to be complete.
Hints:
Counting by visiting every node is a three-line recursion: a subtree has 1 + count(left) + count(right) nodes. Get that working first.
In a complete tree, walk only left edges to get one depth and only right edges to get another. If the two depths of a subtree match, that subtree is *perfect* and holds exactly 2^depth − 1 nodes — no visit needed.
When the two depths differ, recurse into both children — but one of them is always perfect and resolves instantly, so only one true recursion survives per level: O(log n) levels, each paying an O(log n) depth walk.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [1, 2, 3, 4, 5, 6]
Expected output: 6