Count Complete Tree Nodes
Easy · Trees · about 15 minutes
Asked at Google, Amazon, Microsoft, Adobe, Meta, Canva, Electronic Arts, Autodesk.
The binary tree is complete: each level is full, except perhaps the deepest, whose nodes are packed to the left. Count its nodes using fewer than O(n) steps.