Lowest Common Ancestor Implemented with Stack
MediumAsked in:Amazon•Stage:Onsite
treestackhash_table
Problem Statement
Given a rooted binary tree and two distinct node values, find the value of their lowest common ancestor (LCA) using an iterative approach that employs a stack (and optionally a hash table for parent tracking). The solution must run efficiently for large trees.
Input Format
The input consists of: 1) an integer n, the number of nodes in the tree. 2) n lines each containing three integers: node_value left_child_value right_child_value (use -1 if a child is null). 3) two integers u and v representing the values of the nodes whose LCA is to be found. All node values are unique.
Output Format
Output a single integer – the value of the lowest common ancestor of nodes u and v. If either node does not exist, output -1.
Constraints
- 1 <= n <= 10^5
- All node values are distinct integers within 32-bit signed range
- The tree is a valid binary tree (no cycles)
- u != v and both u and v are present in the tree