Lowest Common Ancestor in Binary Search Tree

[jsartisan]

Info

difficulty: medium
title: Lowest Common Ancestor in Binary Search Tree
type: question
template: typescript
tags: javascript, blind75, binary-search-tree, recursion

Question

Given a binary search tree (BST) where all node values are unique, and two nodes p and q, find their lowest common ancestor (LCA).

The lowest common ancestor of two nodes is defined as the deepest node in the tree that has both nodes as descendants. A node can be considered a descendant of itself.

Constraints:

• 2 ≤ Number of nodes in the tree ≤ 100
• -100 ≤ Node values ≤ 100
• p ≠ q
• Both p and q exist in the BST

Examples:

// Example 1:
//        5
//      /   \
//     3     8
//    / \   / \
//   1   4 7   9
//    \
//     2
const root1 = createTree([5, 3, 8, 1, 4, 7, 9, null, 2]);
const p1 = findNode(root1, 3);
const q1 = findNode(root1, 8);
console.log(lowestCommonAncestor(root1, p1, q1)?.val);
// Output: 5

// Example 2:
//        5
//      /   \
//     3     8
//    / \   / \
//   1   4 7   9
//    \
//     2
const root2 = createTree([5, 3, 8, 1, 4, 7, 9, null, 2]);
const p2 = findNode(root2, 3);
const q2 = findNode(root2, 4);
console.log(lowestCommonAncestor(root2, p2, q2)?.val);
// Output: 3
// Explanation: Node 3 is the LCA since it's the parent of 4

Template

index.ts

export 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;
  }
}

export function lowestCommonAncestor(root: TreeNode | null, p: TreeNode | null, q: TreeNode | null): TreeNode | null {

}

index.test.ts

import { TreeNode, lowestCommonAncestor } from './index';

describe('lowestCommonAncestor', () => {
  // Helper function to create tree from array
  function createTree(arr: (number | null)[]): TreeNode | null {
    if (!arr.length) return null;

    const root = new TreeNode(arr[0]!);
    const queue = [root];
    let i = 1;

    while (queue.length && i < arr.length) {
      const node = queue.shift()!;

      if (i < arr.length && arr[i] !== null) {
        node.left = new TreeNode(arr[i]!);
        queue.push(node.left);
      }
      i++;

      if (i < arr.length && arr[i] !== null) {
        node.right = new TreeNode(arr[i]!);
        queue.push(node.right);
      }
      i++;
    }

    return root;
  }

  // Helper function to find node with given value
  function findNode(root: TreeNode | null, val: number): TreeNode | null {
    if (!root) return null;
    if (root.val === val) return root;
    return findNode(root.left, val) || findNode(root.right, val);
  }

  test('Example 1: Nodes in different subtrees', () => {
    const root = createTree([5, 3, 8, 1, 4, 7, 9, null, 2]);
    const p = findNode(root, 3)!;
    const q = findNode(root, 8)!;
    expect(lowestCommonAncestor(root, p, q)?.val).toBe(5);
  });

  test('Example 2: One node is ancestor of other', () => {
    const root = createTree([5, 3, 8, 1, 4, 7, 9, null, 2]);
    const p = findNode(root, 3)!;
    const q = findNode(root, 4)!;
    expect(lowestCommonAncestor(root, p, q)?.val).toBe(3);
  });

  test('Root is LCA', () => {
    const root = createTree([5, 3, 8]);
    const p = findNode(root, 3)!;
    const q = findNode(root, 8)!;
    expect(lowestCommonAncestor(root, p, q)?.val).toBe(5);
  });

  test('Nodes in same subtree', () => {
    const root = createTree([5, 3, 8, 1, 4]);
    const p = findNode(root, 1)!;
    const q = findNode(root, 4)!;
    expect(lowestCommonAncestor(root, p, q)?.val).toBe(3);
  });

  test('Deep nodes', () => {
    const root = createTree([5, 3, 8, 1, 4, 7, 9, null, 2]);
    const p = findNode(root, 2)!;
    const q = findNode(root, 4)!;
    expect(lowestCommonAncestor(root, p, q)?.val).toBe(3);
  });

  test('Negative values', () => {
    const root = createTree([-5, -10, 0, -15, -8]);
    const p = findNode(root, -15)!;
    const q = findNode(root, -8)!;
    expect(lowestCommonAncestor(root, p, q)?.val).toBe(-10);
  });
});

[github-actions[bot]]

244 - Pull Request updated.