Start learning free

LESSON 344 OF 442 · BINARY TREES

Lowest Common Ancestor in a BST in TypeScript: Iterative O(h) Walk

Practice O(n) Read the full explanation

Given the root of a binary search tree (BST) and two values p and q that are both in the tree, return the value of their lowest common ancestor.

The lowest common ancestor of p and q is the deepest node that has both of them in its subtree. A node counts as its own ancestor: if the node holding p is above the node holding q, the answer is p.

In a BST, every value in a node's left subtree is smaller than the node's value, and every value in its right subtree is larger.

The trees below are written in level order (top to bottom, left to right), with null for a missing child.

 

Example 1:

        6
      /   \
     2     8
    / \   / \
   0   4 7   9
      / \
     3   5

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: 2 is in the left subtree of 6 and 8 is in its right subtree, so 6 is the deepest node that has both below it.

Example 2:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: 4 is in the subtree of 2, and a node counts as its own ancestor.

Example 3:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 5, q = 3
Output: 4
Explanation: 3 and 5 are the two children of 4, one on each side.

 

Constraints:

  • The number of nodes in the tree is in the range [1, 1000].
  • Each node value is between -104 and 104, and all values are different.
  • p and q are both values of nodes in the tree. They can be equal.

 

Follow up: Can you find it in O(h) time, where h is the height of the tree, using only O(1) extra space?
STEP 1 OF 6
    Ctrl + Enter to check

    TYPESCRIPT · BINARY TREES

    Lca In Bst in TypeScript, explained

    Problem overview

    The method lowestCommonAncestor receives the root of a binary search tree and two values, p and q, that both occur in the tree. It returns the value of their lowest common ancestor: the deepest node that has both values in its subtree. A node counts as its own ancestor, so if one value sits above the other, the answer is the upper one. The two values may even be equal.

    Take the tree [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5]. For 2 and 8 the answer is 6, since 2 is in the left subtree of 6 and 8 in the right. For 2 and 4 the answer is 2, since 4 is below 2. For 5 and 3 the answer is 4, their shared parent, which has 3 on its left and 5 on its right.

    Approach: let the values choose the direction

    In a general binary tree, finding a common ancestor means searching both subtrees. A binary search tree gives more information: everything in a node's left subtree is smaller than the node, and everything in its right subtree is larger. So at any node, comparing p and q with the node's value says where they are.

    • If both are smaller than the node's value, both are in the left subtree, and so is the lowest common ancestor. Move left.
    • If both are larger, move right.
    • Otherwise they are on different sides of the node, or one of them is the node itself. Going down either way would leave one value behind, so this node is the answer.

    The root is above everything, so it is always a common ancestor. The walk goes down while the current node is not the lowest one, and stops at the first node that splits the two values. Each step goes one level down, so the walk takes at most as many steps as the tree is tall.

    For 5 and 3: the root 6 is larger than both, so move left to 2. Both are larger than 2, so move right to 4. Now 5 is larger than 4 and 3 is smaller, so they split, and the answer is 4.

    Step by step

    1. Declare node with let and set it to root. It changes as we walk, and TypeScript gives it the type of root, TreeNode | null.
    2. Loop with while (node), which stops when node is null. Inside the loop, TypeScript knows node is a real node, so its fields can be read.
    3. Both values smaller: if p < node.val && q < node.val, set node to node.left.
    4. Both values larger: with else if, set node to node.right.
    5. Otherwise return node.val. The values split here, or one of them equals node.val.
    6. Return -1 after the loop. Both values are in the tree, so the loop always returns first, but the line makes every path return a number, as the signature promises.

    The solution in TypeScript

    class Solution {
    lowestCommonAncestor(root: TreeNode | null, p: number, q: number): number {
        let node = root;
        while (node) {
            if (p < node.val && q < node.val) {
                node = node.left;
            } else if (p > node.val && q > node.val) {
                node = node.right;
            } else {
                return node.val;
            }
        }
        return -1;
    }
}

    The TypeScript details worth knowing:

    • Type inference. let node = root; has no annotation, because TypeScript infers TreeNode | null from root. Assigning node.left and node.right, which are also TreeNode | null, is allowed.
    • Narrowing with while (node). A node object is truthy and null is falsy, so the loop condition checks for null. Inside the body, the compiler treats node as a TreeNode. This is a compile-time convenience only. The safety at run time comes from the condition itself.
    • The parameters are values, not nodes. p and q are numbers, so they are compared directly with node.val. In versions of this problem where they are nodes, you would compare p.val and q.val.
    • Why the last return -1 is needed. The compiler can't know that the loop always returns. Without a final return, the function could return undefined on some path.
    • Iteration instead of recursion. The loop keeps only the single variable node, so there is no call stack to grow.

    Complexity

    Time: O(h), where h is the height of the tree. Each pass moves down one level and the walk never goes back up. For a balanced tree of 1,000 nodes that is about 10 steps. For a tree shaped like a list, h equals the number of nodes.

    Space: O(1). Only the variable node is kept.

    Edge cases and common mistakes

    • One value is an ancestor of the other. For 2 and 4 in the example tree, the walk stops at 2: p < node.val is false, and p > node.val is false, so the else returns 2.
    • Equal values. With p = q = 7, the walk goes right at 6 and then reaches 7. Neither strict comparison holds there, so the answer is 7.
    • A single-node tree. The root is the answer for any p and q, which must both equal its value.
    • Using <= and >=. Non-strict comparisons let the walk move past the node that holds p or q. For 2 and 4 in the example tree, the walk would leave 2 to the right, then turn left at 4 and run off the tree, so the method would return -1 instead of 2.
    • Comparing only one value. Moving by p alone ignores where q is, and can go below the split point.
    • Ignoring the BST property. A search of both subtrees works for any tree but costs O(n). The ordered values are what let each step discard one subtree.

    Testing

    On the tree [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5]:

    • p = 2, q = 8 gives 6.
    • p = 2, q = 4 gives 2.
    • p = 5, q = 3 gives 4.
    • p = 7, q = 7 gives 7.
    • p = 0, q = 5 gives 2.
    • p = 3, q = 9 gives 6.
    Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free