Lowest Common Ancestor of BST
Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST. The lowest common ancestor is the node with the largest depth which is the ancestor of both nodes.
Constraints:
- All the values in the BST are unique.
- p and q are different nodes in the BST.
- p and q exist in the BST.
Examples:
Input: [6,2,8,0,4,7,9,null,null,3,5], 2, 8
Output: 6
Explanation: The lowest common ancestor of nodes 2 and 8 is 6.
Solutions
Recursive Approach
This solution uses a recursive approach to find the lowest common ancestor of two nodes in a binary search tree. It checks if the current node is one of the given nodes, and if so, returns the current node. If not, it recursively checks the left and right subtrees. If both left and right subtrees return a node, it means the current node is the lowest common ancestor, so it returns the current node. Otherwise, it returns the non-null node.
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) return null;
if (root.val == p.val || root.val == q.val) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null) return root;
return left != null ? left : right;
}
}Follow-up:
What if the tree is not a binary search tree?
