You’re interviewing for a backend or data engineering role at a FAANG-level company. The interviewer describes a real product scenario:
A large-scale system represents hierarchical relationships such as:
- organization charts
- permission trees
- feature dependency graphs
- UI component hierarchies
These relationships are modeled using a binary tree, where each node represents an entity. For many operations such as authorization checks, dependency resolution, or UI rendering, the system needs to determine the closest shared ancestor between two entities.
The platform receives a binary tree along with references to two nodes in that tree. It must efficiently identify the lowest common ancestor (LCA) of those two nodes.
This is a common practice coding problem for DSA question might ask in Google, Amazon, Netflix, Meta, Apple, Microsoft, Uber, and Bloomberg interviews.
Your Task
Given the root of a binary tree and two distinct nodes p and q, return their lowest common ancestor (LCA).
The LCA of two nodes p and q is defined as the lowest node in the tree that has both p and q as descendants, where a node can be a descendant of itself.
Input Format
root: the root node of a binary treep: reference to the first nodeq: reference to the second node
Each node is defined as:
TreeNode { int val; TreeNode left; TreeNode right; }
Output Format
- Return the node representing the lowest common ancestor of
p and q
Examples
Example 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4]
p = 5
q = 1
Output: 3
Example 2:
Input: root = [3,5,1,6,2,0,8,null,null,7,4]
p = 5
q = 4
Output: 5
Example 3:
Input: root = [1,2]
p = 1
q = 2
Output: 1