Tree DFS
LC #235Medium
Lowest Common Ancestor of BST
Tree DFS
AmazonMetaMicrosoftGoogleProblem
Find the lowest common ancestor (LCA) of two nodes p and q in a BST. The LCA is the lowest node that has both p and q as descendants.
treedfsbst
Constraints
- ›2 ≤ number of nodes ≤ 10⁵
- ›-10⁹ ≤ node.val ≤ 10⁹
- ›p and q exist in the BST
- ›p ≠ q
Example
Input
root = [6,2,8,0,4,7,9], p = 2, q = 8Output
6Why
LCA of 2 and 8 is 6 (root) since one is in left subtree, other in right