Lowest Common Ancestor of a Binary Tree
The key idea
Recurse down the tree. A node is the lowest common ancestor when p and q split below it: one target is found in its left subtree and the other in its right subtree. The other case is when the node itself is p or q and the second target lies somewhere beneath it, because a node counts as a descendant of itself.
Problem
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes p and q in the tree. The lowest common ancestor is defined as the lowest node in the tree that has both p and q as descendants, where a node is allowed to be a descendant of itself. Both p and q are guaranteed to exist in the tree, and all node values are unique.
Constraints
- The number of nodes in the tree is in the range [2, 10^5].
- -10^9 <= Node.val <= 10^9
- All Node.val are unique.
- p != q
- p and q will exist in the tree.
Examples
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Input: root = [1,2], p = 1, q = 2
Output: 1
Complexity
Time: O(n) Space: O(h)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Tree / Recursion problems
- Balanced Binary TreeEASY
- Binary Tree CamerasHARD
- Binary Tree Inorder TraversalEASY
- Binary Tree Maximum Path SumHARD
- Binary Tree PathsEASY
- Binary Tree Postorder TraversalEASY
- Binary Tree Preorder TraversalEASY
- House Robber IIIMEDIUM
- Construct Binary Tree from Inorder and Postorder TraversalMEDIUM
- Construct Binary Tree from Preorder and Inorder TraversalMEDIUM
- Convert BST to Greater TreeMEDIUM
- Count Complete Tree NodesEASY