โ† Visa questions

Height of a full binary tree in O(1)

Filed under Visa

Free read 3 of 3

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.

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

  1. 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.

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.