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:
def lowestCommonAncestor(self, root:
'TreeNode', p:
'TreeNode', q:
'TreeNode') -> 'TreeNode':
if not root:
return None if root.val == p.val or root.val == q.val:
return root left = self.lowestCommonAncestor(root.left, p, q) right = self.lowestCommonAncestor(root.right, p, q) if left and right:
return root return left if left else rightFollow-up:
What if the tree is not a binary search tree?
