Lowest Common Ancestor Implemented with Stack
Amazonâ—Ź MediumINTERNNEW GRADONSITE INTERVIEWProblem statement
Given a binary tree and two distinct nodes p and q that both exist in the tree, return their lowest common ancestor. A node counts as its own descendant.
Use a stack to traverse the tree and build a parent map. Starting from p, walk to the root and record its ancestors. Then walk upward from q; the first recorded ancestor is the answer.
The practice interface provides root as a level-order array of strings. Each non-null entry holds an integer, and "null" marks a missing child. The values p and q identify the target nodes.
The problem statement continues
ProExamples
Example 1
root = ["10","5","15","3","7","12","18","null","4","6","8"]p = 3q = 8return = 5Node 5 is the lowest node that has both 3 and 8 in its subtree.
Original screenshot from the interview report
ProFastPrep Pro
Reported in 1 Amazon interview this weekUnlock this recently reported problem
FastPrep Pro gives you full access to interview problems reported within the last week.
- Full problem statement and constraints
- 1 more worked example, explained
- Guided hints and editorial
- Run your code on real test cases
$8.25/month
$99 billed yearly — or $19 month-to-month. Cancel anytime.
Free plan — 2 of 2 free unlocks used this week