Lowest Common Ancestor of a Binary Search Tree medium

Problem Statement

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example 1

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

Example 2

Input: root = [6,2,8,0,4,7,9,null,null,null,null,null,null,null,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Steps and Explanation

The key to efficiently solving this problem lies in leveraging the properties of a Binary Search Tree. In a BST, the value of a node is greater than all values in its left subtree and smaller than all values in its right subtree.

We can use a recursive approach:

1. Base Case: If the root is None, there's no LCA, so return None.
2. Check if p and q are found: If p.val and q.val are both smaller than root.val, the LCA must be in the left subtree. If both are larger, it's in the right subtree.
3. LCA Found: If one value is smaller and the other is larger than root.val, then the root itself is the LCA.
4. Recursive Calls: Recursively call the function on the appropriate subtree (left or right).

Code

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root:
            return None

        if p.val < root.val and q.val < root.val:
            return self.lowestCommonAncestor(root.left, p, q)
        elif p.val > root.val and q.val > root.val:
            return self.lowestCommonAncestor(root.right, p, q)
        else:
            return root

Complexity Analysis

• Time Complexity: O(N), where N is the number of nodes in the BST. In the worst case, we might traverse the entire tree.
• Space Complexity: O(H), where H is the height of the BST. This is due to the recursive call stack. In the worst case (a skewed tree), H can be equal to N, but for a balanced BST, H is log₂(N).

This solution provides a clear and efficient way to find the lowest common ancestor in a binary search tree. The recursive approach takes advantage of the BST's inherent structure, leading to a time-efficient solution. Remember to handle the base case of an empty tree appropriately.