hardTreesPure DSA~30 min
Lowest Common Manager of Two Employees
An org chart is a binary tree. Given two employees, find their lowest common manager — the deepest node that has both employees somewhere in its subtree.
Problem
Given the root of a binary tree and two distinct nodes p and q present in the tree, return their lowest common ancestor (LCA): the deepest node that is an ancestor of both p and q (a node is an ancestor of itself).
Input
A binary tree root and two node references p and q.
Output
The LCA node.
Constraints
- 2 <= number of nodes <= 10^5
- All node values are unique.
- p and q both exist in the tree.
Examples
Example 1
Input
root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output
3
5 and 1 sit in different subtrees of 3.
Example 2
Input
root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output
5
4 lies in 5's subtree, so 5 is its own-and-ancestor LCA.