Start learning free

LESSON 344 OF 442 · BINARY TREES

Lowest Common Ancestor in a BST in Scala: An 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

    SCALA · BINARY TREES

    Lca In Bst in Scala, 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 p sits above q, the answer is p. The two values may also be equal.

    The tree in the examples is:

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

    For 2 and 8 the answer is 6: one value is in the left subtree and the other in the right, and no deeper node has both. For 2 and 4 the answer is 2, because 4 lies below 2 and a node is its own ancestor. For 5 and 3 the answer is 4, the node whose two children they are.

    Approach: let the values choose the direction

    In a binary search tree, every value in a node's left subtree is smaller than the node's value, and every value in its right subtree is larger. That ordering tells us where a value lives without searching.

    Start at the root. It is above everything, so it is a common ancestor, but maybe not the lowest. Compare p and q with the current node's value:

    • If both are smaller, both live in the left subtree, so the lowest common ancestor is there too. Move to the left child.
    • If both are larger, move to the right child.
    • Otherwise the values are on different sides of the node, or one of them equals the node's value. Going down to either side would leave one of the values behind, and this node has both below it (or is one of them). This is the answer.

    The walk moves one level per step and never goes back, so it takes at most as many steps as the tree is tall, O(h). It needs no recursion and no stack, so the extra space is O(1): this meets the follow-up's goal.

    Trace p = 5, q = 3 on the tree above. At 6, both are smaller, so go left to 2. At 2, both are larger, so go right to 4. At 4, 3 is smaller and 5 is larger: they are on different sides, so the answer is 4.

    Step by step

    1. Declare node with var and set it to root. It changes as the walk goes down.
    2. Loop while node != null. Each pass looks at one node and either stops or moves down by one level.
    3. Both smaller: go left. If p < node.value && q < node.value, set node = node.left.
    4. Both larger: go right. Otherwise, in an else if, when p > node.value && q > node.value, set node = node.right.
    5. Otherwise return the node's value. The else covers values on both sides and the case where one of them is this very node. In both cases it is the deepest node with both below it or at it.
    6. Return -1 after the loop. Because both values are in the tree, the loop always returns first. The line exists because the method must produce an Int on every path.

    The solution in Scala

    class Solution {
    def lowestCommonAncestor(root: TreeNode, p: Int, q: Int): Int = {
        var node = root
        while (node != null) {
            if (p < node.value && q < node.value) {
                node = node.left
            } else if (p > node.value && q > node.value) {
                node = node.right
            } else {
                return node.value
            }
        }
        return -1
    }
}

    The Scala details worth knowing:

    • Values, not nodes. Here p and q are Ints, and the method returns an Int. There is no need to find the nodes first. The comparison with node.value is enough.
    • if / else if / else as statements. Each branch either assigns to node or leaves the method with return. The if is used for its effects here, and its value is dropped.
    • return inside the loop. A value found in the middle of a loop can only leave the method through return. The final return -1 is the other exit, which the loop never reaches for valid input.
    • null children. A missing child is null, so node != null asks whether there is still a node to look at.
    • var node = root makes a new reference to the root, so reassigning node never changes the tree.

    Complexity

    Time: O(h), where h is the height of the tree. Each pass moves one level down, and the walk stops at the lowest common ancestor, which is no deeper than the deepest leaf. For a balanced tree this is about log n. For a tree shaped like a list it is n.

    Space: O(1). Only the reference node is kept. A recursive version would use O(h) stack space for the same walk.

    Edge cases and common mistakes

    • One value is an ancestor of the other. For 2 and 4 the walk reaches node 2, where 2 is not smaller than 2. Neither branch for "both smaller" or "both larger" applies, so the method returns 2.
    • Equal values. With p = q = 7, the walk goes right at 6, reaches 8, goes left to 7 and stops there, since 7 < 7 is false and so is 7 > 7. The answer is 7.
    • A single-node tree. The only possible values are the root's own, and the method returns it right away.
    • Using <= or >= in the first two tests. This would send the walk below a node that equals p or q, past the real answer.
    • Using || instead of &&. The walk must move only when both values are on the same side. With || it would move when just one is, losing the other.
    • Searching the whole tree. A general binary tree needs a search of both subtrees. The ordering of a BST removes that need.
    • Different sides with unequal depths. For 0 and 5 the answer is 2, and for 9 and 7 the answer is 8, whatever the depths of the values.

    Testing

    On the tree from the examples:

    • 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 = 9, q = 7 gives 8.
    Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free