38 / 75
Medium
Lowest Common Ancestor of BST
#38treebstbinary-searchdfs
Use BST property: if p and q split at node (one left, one right), that node is LCA.
Example:
Input:
root=[6,2,8,0,4,7,9,null,null,3,5], p=2, q=8Output:
6 (split point)Common Mistakes:
- Not leveraging BST property (treating it like regular binary tree)
- Using recursive approach when iterative is simpler
- Forgetting that node can be ancestor of itself
- Not handling case where p or q is the LCA
Notes:
BST property makes this easier than regular binary tree LCA. Time O(h), Space O(1) iterative. Can also solve recursively.
💻
Java Solution Hidden
Enable “Show Full Solution” to view the code
Use BST property: if p and q split at node (one left, one right), that node is LCA.
Example:
Input:
root=[6,2,8,0,4,7,9,null,null,3,5], p=2, q=8Output:
6 (split point)Common Mistakes:
- Not leveraging BST property (treating it like regular binary tree)
- Using recursive approach when iterative is simpler
- Forgetting that node can be ancestor of itself
- Not handling case where p or q is the LCA
Notes:
BST property makes this easier than regular binary tree LCA. Time O(h), Space O(1) iterative. Can also solve recursively.
38/75
Lowest Common Ancestor of BST