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

The key to solving this problem efficiently lies in leveraging the properties of a Binary Search Tree. In a BST:

  1. If both p and q are less than the current node's value (root.val): The LCA must lie in the left subtree.
  2. If both p and q are greater than the current node's value (root.val): The LCA must lie in the right subtree.
  3. Otherwise: The current node is the LCA.

Explanation

The algorithm recursively traverses the tree. At each node, it compares the values of p and q with the node's value. This comparison guides the search towards the subtree where the LCA resides. The recursion continues until the LCA is found.

Code

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = val === undefined ? 0 : val;
        this.left = left === undefined ? null : left;
        this.right = right === undefined ? null : right;
    }
}

function lowestCommonAncestor(root: TreeNode | null, p: TreeNode, q: TreeNode): TreeNode | null {
    if (!root) return null;

    if (p.val < root.val && q.val < root.val) {
        return lowestCommonAncestor(root.left, p, q); // Both p and q are in the left subtree
    } else if (p.val > root.val && q.val > root.val) {
        return lowestCommonAncestor(root.right, p, q); // Both p and q are in the right subtree
    } else {
        return root; // Current node is the LCA
    }
};

Complexity

  • Time Complexity: O(H), where H is the height of the BST. In the worst case (a skewed tree), H can be equal to N (the number of nodes), resulting in O(N) time complexity. However, in a balanced BST, H is log₂(N), leading to O(log N) time complexity.

  • Space Complexity: O(H) in the worst case due to the recursive call stack. This is O(N) for a skewed tree and O(log N) for a balanced tree.