Count Complete Tree Nodes
The key idea
A complete tree is *almost* perfect. Measure the left-spine height
lh (keep going left) and the right-spine height rh (keep going right). If lh == rh the subtree is perfect, so it holds exactly 2^lh - 1 nodes with no recursion. Otherwise recurse into both children. Only one side keeps recursing per level, giving O(log^2 n).Problem
Given the root of a complete binary tree, return the number of nodes in the tree.
By definition, in a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. The last level h can have between 1 and 2^h nodes inclusive.
Design an algorithm that runs in less than O(n) time complexity.
Constraints
- The number of nodes in the tree is in the range
[0, 5 * 10^4]. 0 <= Node.val <= 5 * 10^4- The tree is guaranteed to be complete.
Examples
Input: root = [1,2,3,4,5,6]
Output: 6
Input: root = []
Output: 0
Input: root = [1]
Output: 1
Complexity
Time: O(log^2 n) Space: O(log n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Tree / Recursion problems
- Balanced Binary TreeEASY
- Binary Tree CamerasHARD
- Binary Tree Inorder TraversalEASY
- Binary Tree Maximum Path SumHARD
- Binary Tree PathsEASY
- Binary Tree Postorder TraversalEASY
- Binary Tree Preorder TraversalEASY
- House Robber IIIMEDIUM
- Construct Binary Tree from Inorder and Postorder TraversalMEDIUM
- Construct Binary Tree from Preorder and Inorder TraversalMEDIUM
- Convert BST to Greater TreeMEDIUM
- Count Good Nodes in Binary TreeMEDIUM