Lowest Common Ancestor of a Binary Search Tree

Lowest Common Ancestor of Binary Search Tree

Asked in: Amazon, Microsoft

Difficulty: Medium

Understanding the problem

Problem Description: Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

Problem Note

Lowest Common Ancestor: The lowest common ancestor is defined between two nodes node1 and node2 as the lowest node in T that has both node1 and node2 as descendants (where we allow a node to be a descendant of itself).
All of the nodes’ values will be unique.
node1 and node2 are different and both values will exist in the BST.
You can use extra memory, helper functions, and can modify the node struct but, you can’t add a parent pointer.

Example 1

The node structure passed to your function will be

class TreeNode
{
    int data
    TreeNode left
    TreeNode right
}

You may try solving the problem here

Solutions

We can solve this using the approaches as discussed while finding LCA in a binary tree. But, a binary search tree’s property could be utilized, to come up with a better algorithm with lesser complexity.

Recursive Approach
Iterative Approach

1. Recursive Approach

The lowest common ancestor for the two nodes node1 and node2 would be the last ancestor node common to both of them. Here last is defined in terms of the depth of the node .

If we boil down the above explanation then we could justify it in this form →

LCA is the last root satisfying min(node1, node2) <= root <= max(node1,node2) where node1 and node2 will be in the subtree of the root while traversing top to bottom in the tree.

Solution Steps

Start traversing the tree from the root node.
If both the nodes node1 and node2 are in the right subtree, then recursively move to the right subtree.
If both the nodes node1 and node2 are in the left subtree, then recursively move to the left subtree.
Otherwise, the current node is the lowest common ancestor.

Pseudo Code

TreeNode lowestCommonAncestor(TreeNode root, TreeNode node1, TreeNode node2) {
    if (node1.val > root.val and node2.val > root.val) {
        // If both node1 and node2 are greater than parent
        return lowestCommonAncestor(root.right, node1, node2)
    } 
    else 
    if (node1.val < root.val and node2.val < root.val) {
        // If both node1 and node2 are lesser than parent
        return lowestCommonAncestor(root.left, p, q)
    } else {
        // We have found the split point, i.e. the LCA node.
        return root
    }
}

Complexity Analysis

Time Complexity: O(log n) if the tree is balanced binary search tree otherwise, in the worst case, the complexity could be O(n)

Space Complexity: O(n)

Critical Ideas to Think

Why did we reduce our search space to the left subtree if the value of root is greater than both the values of the nodes?
How will the algorithm react if either of the nodes would not be present in the tree?

2. Iterative Approach

If we look closely the recursive solution and try to implement the same logic iteratively then you will find that we don’t need to backtrack to find the LCA node and just have to traverse down the tree and look for the split point of node1 and node2 which could be done without using any stack or queue.

Solution steps

Start traversing the tree from the root node.
If both the nodes node1 and node2 are in the right subtree, then iteratively move to the right subtree.
If both the nodes node1 and node2 are in the left subtree, then iteratively move to the left subtree.
Otherwise, the current node is the lowest common ancestor.

Pseudo Code

TreeNode lowestCommonAncestor(TreeNode root, TreeNode node1, TreeNode node2) {
    // Traverse the tree
    while (root is not null) {
        if (node1.val > root.val and node2.val > root.val) {
            // If both node1 and node2 are greater than parent
            root = root.right
        } 
        else 
        if (node1.val < root.val and node2.val < root.val) {
            // If both node1 and node2 are lesser than parent
            root = root.left
        } 
        else {
            // We have found the split point, i.e. the LCA node.
            return node
        }
    }
    return null
}