Count Complete Tree Nodes

Intuition

Walking straight down the left edge of a complete tree gives the height along the shortest-filled side, and walking straight down the right edge gives the height along the possibly-shorter side. If those two heights match, the subtree is perfect and packs exactly 2^h - 1 nodes, which we compute instantly with a bit shift. If they differ, the last level is only partially filled, so we recurse into both children and add one for the current node. The key win is that each recursive call collapses at least one branch into the O(1) formula, so the recursion depth is O(log n) and each level costs O(log n) to measure a spine. That yields O(log^2 n) work overall instead of touching every node.

Algorithm walkthrough

1. 1If the node is null, return 0.
2. 2Walk only left children counting steps to get leftHeight, then walk only right children to get rightHeight.
3. 3If leftHeight == rightHeight, the subtree is perfect: return (1 << leftHeight) - 1.
4. 4Otherwise the last row is partial, so return 1 + countNodes(left) + countNodes(right).
5. 5Each recursion resolves one side by formula, giving O(log n) recursive calls.
6. 6Multiplying the O(log n) spine measurement by O(log n) recursion depth gives O(log^2 n).

Implementation

class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0

        left_height = 0
        node = root
        while node:
            left_height += 1
            node = node.left

        right_height = 0
        node = root
        while node:
            right_height += 1
            node = node.right

        if left_height == right_height:
            return (1 << left_height) - 1

        return 1 + self.countNodes(root.left) + self.countNodes(root.right)