Lowest Common Ancestor of a Binary Tree
Medium · Trees · Tree · DFS · Recursion
Problem
Given a binary tree and two values p and q present in it, return the value of their lowest common ancestor — the deepest node having both as descendants. A node counts as a descendant of itself.
The tests build the tree and look the nodes up by value for you.
Examples
Input: root = [3,5,1,6,2,0,8,None,None,7,4], p = 5, q = 1 Output: 3
The root is the deepest node containing both.
Input: root = [3,5,1,6,2,0,8,None,None,7,4], p = 5, q = 4 Output: 5
5 is an ancestor of 4, and a node is its own descendant.
Constraints
- 2 <= number of nodes <= 10^5
- All values are unique
- p != q, and both exist in the tree
Approaches
- Record parents, then walk up — time O(n), space O(n)
Related problems
Start free on Cariara · Coding problems · System design studio
