Given two nodes, p and q, we’re asked to find the lowest common ancestor of each node in a binary search tree. The nodes themselves can also be the lowest common ancestor. Given that this is a binary search tree, we can use the values of p and q to direct our search either left or right. But, if the values of p and q are not greater than the current node or less than the current node, we know that we’ve found the lowest common ancestor.
The solution is as follows:
class Solution:
def lowestCommonAncestor(self, root: Optional[TreeNode], p: TreeNode, q: TreeNode) -> Optional[TreeNode]:
if not root:
return
if p.val < root.val and q.val < root.val:
return self.lowestCommonAncestor(root.left, p, q)
if p.val > root.val and q.val > root.val:
return self.lowestCommonAncestor(root.right, p, q)
else:
return root_ Time Complexity:
O(n) - Where n is the number of nodes in the binary search tree.
_ Space Complexity:
O(n) - Our recursive function can be called n times.