Minimum height of a tree
Filed under Amazon
Free read 2 of 3Verify if duplicate values are allowed in the binary tree.
The question
Find the minimum height of a binary tree given its inorder and level order traversal.
Constraints
- 1 <= Number of nodes <= 1000
- Traversals represent a valid binary tree.
Examples
- Input
- inorder = [4, 2, 5, 1, 3], level = [1, 2, 3, 4, 5]
- Output
- 3
- Why
- Reconstruct the tree from traversals and compute its minimum height.
Approach
Verify if duplicate values are allowed in the binary tree.
Generate all possible trees matching the traversals and find the minimum height (exponential time).
Reconstruct the tree recursively using inorder and level order arrays, then compute the minimum depth from root to any leaf.
Single node tree or skewed tree (linked-list-like structure).
Tips
- What they are testing: Test skewed trees versus perfectly balanced trees.
- Common mistake: Incorrectly filtering the level order traversal for left and right subtrees without preserving element order.
Related Amazon questions
Collected from public candidate posts and coding forums. Updated Nov 2026.