Height of a full binary tree in O(1)
Filed under Visa
Free read 3 of 3A full binary tree has N = 2^h+1 - 1 nodes where h is the height. A complete binary tree is filled level by level.
The question
Define the difference between a complete and full binary tree. Given the total number of nodes N in a full binary tree, calculate its height in O(1) time.
Constraints
- Full binary tree: every node has 0 or 2 children.
- Complete binary tree: all levels filled except possibly the last, which is filled left-to-right.
- Time complexity must be O(1).
- N is the total number of nodes.
Examples
- Input
- N = 7
- Output
- Height = 2
- Why
- A full binary tree with 7 nodes has 3 levels (root at level 0), so height is 2.
Approach
A full binary tree has N = 2^h+1 - 1 nodes where h is the height. A complete binary tree is filled level by level.
For a full binary tree, the number of nodes N is always odd. The relationship is N = 2^(h+1) - 1.
Rearrange the formula: N + 1 = 2^(h+1), then log2(N + 1) = h + 1, so h = log2(N + 1) - 1.
Tips
- What they are testing: Tests your understanding of tree properties versus algorithmic traversal.
- Common mistake: Confusing the definition of 'full' (every node has 0 or 2 children) with 'perfect' or 'complete'.
Related Visa questions
Collected from public candidate posts and coding forums. Updated Nov 2026.