Coding Interview Questions | Lowest Common Ancestor

December 24th, 2023

Introduction:

This summary will talk about my solution to the lowest common ancestor problem as seen on leetcode here.

Solution:

function lowestCommonAncestor(
  root: TreeNode | null,
  p: TreeNode | null,
  q: TreeNode | null
): TreeNode | null {
  if (!root) {
    return null;
  }
  const visitedNodesSet = new Set<number>();
  const pNodesToVisitStack = [root];

  // Perform DFS to populate visited nodes to get to p val
  while (pNodesToVisitStack.length !== 0) {
    const currentNode = pNodesToVisitStack.pop()!;
    visitedNodesSet.add(currentNode.val);

    if (p.val > currentNode.val && currentNode.right) {
      pNodesToVisitStack.push(currentNode.right);
    } else if (p.val < currentNode.val && currentNode.left) {
      pNodesToVisitStack.push(currentNode.left);
    }
  }

  const qNodesToVisitStack = [root];
  let lowestCommonAncestor = null;
  // Perform DFS to find if p and q share a common ancestor
  while (qNodesToVisitStack.length !== 0) {
    const currentNode = qNodesToVisitStack.pop()!;

    if (visitedNodesSet.has(currentNode.val)) {
      lowestCommonAncestor = currentNode;
    }

    if (q.val > currentNode.val && currentNode.right) {
      qNodesToVisitStack.push(currentNode.right);
    } else if (q.val < currentNode.val && currentNode.left) {
      qNodesToVisitStack.push(currentNode.left);
    }
  }

  return lowestCommonAncestor;
}

Summary:

The solution above uses a Depth-First Search (DFS) approach in two steps to locate the paths from the root to each of the given nodes, p and q.

The function first checks for edge cases where the root is null, and then initializes a set to store visited nodes during the traversal. The DFS is applied separately to both nodes p and q, building paths from the root to each node while checking for matches along the way.

The traversal logic is based on the BST property, navigating to the left or right child nodes depending on the comparison of node values. Once the paths to both nodes are established, the algorithm iterates through one of the paths to find the lowest common ancestor by checking for a match with the other node’s path.