Find LCA of 2 Node in Binary Search Tree in Kotlin | Lowest Common Ancestor

LCA stands for “Lowest Common Ancestor”. In a binary search tree, the LCA of two nodes is the node that is the lowest common ancestor of both nodes and has the greatest value less than or equal to the values of both nodes. For example, consider the following binary search tree:

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

The LCA of nodes 2 and 8 is node 6, since it is the lowest common ancestor of both nodes and has the greatest value less than or equal to both node values. The LCA of nodes 4 and 5 is node 4, since it is the lowest common ancestor of both nodes and has the greatest value less than or equal to both node values.

class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}
fun lowestCommonAncestor(root: TreeNode?, p: TreeNode?, q: TreeNode?): TreeNode? {
    if (root == null || p == null || q == null) {
        return null
    }

    var curr = root
    while (curr != null) {
        if (p.`val` < curr.`val` && q.`val` < curr.`val`) {
            curr = curr.left
        } else if (p.`val` > curr.`val` && q.`val` > curr.`val`) {
            curr = curr.right
        } else {
            return curr
        }
    }
    return null
}
fun main() {
    // Creating the binary search tree
    val root = TreeNode(6)
    root.left = TreeNode(2)
    root.right = TreeNode(8)
    root.left?.left = TreeNode(0)
    root.left?.right = TreeNode(4)
    root.left?.right?.left = TreeNode(3)
    root.left?.right?.right = TreeNode(5)
    root.right?.left = TreeNode(7)
    root.right?.right = TreeNode(9)

    // Finding the LCA of two nodes
    val p = root.left?.left // Node with value 0
    val q = root.left?.right?.right // Node with value 5
    val lca = lowestCommonAncestor(root, p, q)

    // Printing the result
    if (lca != null) {
        println("The LCA of ${p?.`val`} and ${q?.`val`} is ${lca.`val`}.")
    } else {
        println("Either the root or one or both of the input nodes is null.")
    }
}

This function takes the root of a binary search tree and two nodes p and q as input, and returns the LCA of p and q. It first checks if either the root or the input nodes are null, and if so, returns null. Then it traverses the tree iteratively, starting from the root.

During each iteration, it compares the values of the input nodes p and q with the current node curr. If both p and q are smaller than curr, it moves to the left child of curr because the LCA should be in the left subtree. If both p and q are greater than curr, it moves to the right child of curr because the LCA should be in the right subtree. Otherwise, the current node curr is the LCA, so it returns it.

If it reaches the end of the loop without finding the LCA, it returns null.

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

main function creates a binary search tree with the same structure as the example I used in the previous answer, and then calls the lowestCommonAncestor function to find the LCA of two nodes: the node with value 0 and the node with value 5. It then prints the result, which in this case is “The LCA of 0 and 5 is 2.”