Learning Journal

2/15/2024

Lowest Common Ancestor in Binary Search Tree

Tags: algorithms leetcode binary_search_tree

/**
 * Definition for a binary tree node.
 * 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 | null, q: TreeNode | null): TreeNode | null {
	const curVal = root.val;
    const smallVal = p.val < q.val? p.val : q.val;
    const bigVal = p.val > q.val? p.val : q.val;

    if(curVal < smallVal)
        return lowestCommonAncestor(root.right, p, q);
    else if (curVal > bigVal)
        return lowestCommonAncestor(root.left, p, q);
    else return root;
};/**
 * Definition for a binary tree node.
 * 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 | null, q: TreeNode | null): TreeNode | null {
	const curVal = root.val;
    const smallVal = p.val < q.val? p.val : q.val;
    const bigVal = p.val > q.val? p.val : q.val;

    if(curVal < smallVal)
        return lowestCommonAncestor(root.right, p, q);
    else if (curVal > bigVal)
        return lowestCommonAncestor(root.left, p, q);
    else return root;
};

THE PROBLEM

First, let's define what the lowest common ancestor in a binary tree is. It is the node in the middle of 2 subtrees each of which contains the two nodes.

Why? Because, if it is not in the middle, it means the two children nodes are either in its left sub-tree or in its right sub-tree, which means the root of the subtree contains both of them is also the common ancestor and lower than the current node. So, the current node can not be the lowest one.

So, how can we find such node? Start from the root, if the value of the current node is greater than the greatest between the two nodes, we go to the left (it's a binary search tree, they are not in the right). If the value of the current node is smaller than the smallest between the two nodes, we go to the right. If it is in between, we found the node we're looking for.

Revised by ChatGPT

First, let's define the lowest common ancestor (LCA) in a binary search tree. It is the node that is the deepest (or lowest) in the tree and is an ancestor of both given nodes. In other words, it is the node where the paths from the root to each of the two given nodes diverge.

Why is this the case? If the LCA were not the deepest common ancestor, it would imply that both given nodes are either in its left subtree or its right subtree. This would mean that there exists a lower common ancestor, which contradicts the definition of LCA.

So, how can we find the LCA? Starting from the root, if the value of the current node is greater than the larger of the two given nodes, we move to the left subtree (since it's a binary search tree, and the given nodes cannot be in the right subtree). If the value of the current node is smaller than the smaller of the two given nodes, we move to the right subtree. If the value of the current node is between the values of the two given nodes, we have found the LCA.