Solving Lowest Common Ancestor of a Binary Search Tree: Finding a Common Node

The "Lowest Common Ancestor of a Binary Search Tree" problem focuses on finding the lowest (or deepest) common ancestor of two nodes in a BST. The lowest common ancestor is defined as the lowest node in the tree that has both nodes as descendants.

Problem Statement

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

Example

Consider a binary search tree:

The lowest common ancestor of nodes 2 and 8 is 6.

Solution Approach - Iterative Traversal

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 {
  let currentNode = root;

  while (currentNode) {
    if (p.val < currentNode.val && q.val < currentNode.val) {
      currentNode = currentNode.left;
    } else if (p.val > currentNode.val && q.val > currentNode.val) {
      currentNode = currentNode.right;
    } else {
      return currentNode;
    }
  }

  return null;
}

Breaking Down the Solution

• Iterative Search: Iteratively traverse the tree starting from the root.
• Decision Making: If both nodes p and q are smaller than the current node, move to the left subtree. If both are larger, move to the right subtree.
• Finding LCA: The first node where p and q split into different directions is the LCA.

Conclusion

Finding the Lowest Common Ancestor in a BST is a fundamental problem in tree algorithms, demonstrating the efficiency of BST properties in solving search-related queries.