Start learning free

LESSON 344 OF 442 · BINARY TREES

Lowest Common Ancestor in a BST in Kotlin: O(h) Iterative 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

    KOTLIN · BINARY TREES

    Lca In Bst in Kotlin, explained

    Problem overview

    The function lowestCommonAncestor receives the root of a binary search tree and two values, p and q, that are both 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 can also be equal.

    Take the tree with root 6, children 2 and 8, then 0 and 4 under 2, 7 and 9 under 8, and 3 and 5 under 4. For p = 2 and q = 8 the answer is 6: they lie on different sides of the root. For p = 2 and q = 4 the answer is 2, because 4 is in the subtree of 2. For p = 5 and q = 3 the answer is 4, the parent of both.

    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: every value in a node's left subtree is smaller than the node, and every value in its right subtree is larger. So comparing p and q with the current node's value tells where they are without searching.

    Start at the root, which is above every node and is therefore always a common ancestor. Then look at the current node:

    • If both values are smaller than the node, both are in its left subtree, and the lowest common ancestor is there too. Move left.
    • If both are larger, move right for the same reason.
    • Otherwise the values are split: one is smaller and one larger, or one of them equals the node's value. Going down either way would leave one of them behind, so this node is the deepest one that has both below it. This is the answer.

    Each step goes one level down, so the walk takes at most as many steps as the tree is tall.

    In the example tree, for p = 5 and q = 3, the walk starts at 6: both values are smaller, so move left to 2. Both are larger than 2, so move right to 4. Now 5 is larger and 3 is smaller, so the values are split, and the answer is 4.

    Step by step

    1. Declare node with var and set it to root. It changes as the walk goes down. Its type is TreeNode? like root, and it becomes null if the walk goes past a leaf.
    2. Loop while node != null. Inside, Kotlin treats node as non-null (a smart cast), so node.value can be read directly.
    3. Both smaller: if p < node.value && q < node.value, set node to node.left.
    4. Both larger: with else if, if both are greater than node.value, set node to node.right.
    5. Otherwise return node.value. The values are on different sides, or one of them is this node. Both cases make this node the answer.
    6. Return -1 after the loop. The loop always returns first, because p and q are in the tree, but Kotlin needs a function that returns an Int to return a value on every path.

    The solution in Kotlin

    class Solution {
    fun 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 Kotlin details worth a closer look:

    • Nullable children. left and right have the type TreeNode?, so assigning node.left to node is allowed because node is also TreeNode?. var node = root infers that type.
    • Smart cast in the loop. The condition node != null lets the body use node.value and node.left without ?.. This works because node is a local var, and the assignments to it come after the reads in each pass.
    • Values, not nodes. p and q are Int values, and the function returns an Int. There is no need to find the nodes first, and comparing values with < and > is a plain numeric comparison.
    • The -1 at the end. It is unreachable for valid input. Values in the tree can be negative, down to -10,000, so -1 is not a sentinel the caller could use to detect a failure. It is only there for the compiler.
    • else if chains. The branches are tried in order, and only the first true one runs.

    Complexity

    Time: O(h), where h is the height of the tree. Each loop pass moves one level down and does constant work. In a balanced tree h is about log n, and in a tree shaped like a list it is n.

    Space: O(1). The loop uses one reference, node. A recursive version would use O(h) stack space for the same walk.

    Edge cases and common mistakes

    • One value above the other. For p = 2 and q = 4 the walk stops at 2: p < node.value is false there, so neither "both smaller" nor "both larger" holds, and the else branch returns 2.
    • Equal values. With p = 3 and q = 3 the walk follows the path to 3 and returns 3, because a node is its own ancestor.
    • Single-node tree. With a root of 5 and p = q = 5, the else branch returns 5 at once.
    • Using <= in the first two tests. If one of the values equals the node's value, the walk would move past that node, which is the answer, and return a different value.
    • Using || instead of &&. One value smaller than the node doesn't put both in the left subtree. It would send the walk away from the other one.
    • Treating it as a general tree. A search of both subtrees works but ignores the ordering and costs O(n).

    Testing

    All of these use the example tree with root 6.

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