Easy_Question15 : Lowest Common Ancestor in a Binary Search Tree

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

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example 1:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

Example 2:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Example 3:

Input: root = [2,1], p = 2, q = 1
Output: 2

class Node
{
    int data;
    Node left, right;
 
    Node(int item)
    {
        data = item;
        left = right = null;
    }
}
 
class BinaryTree
{
    Node root;
     
/* Function to find LCA of n1 and n2.
The function assumes that both
n1 and n2 are present in BST */
static Node lca(Node root, int n1, int n2)
{
    while (root != null)
    {
        // If both n1 and n2 are smaller
        // than root, then LCA lies in left
        if (root.data > n1 &&
            root.data > n2)
        root = root.left;
 
        // If both n1 and n2 are greater
        // than root, then LCA lies in right
        else if (root.data < n1 &&
                 root.data < n2)
        root = root.right;
 
        else break;
    }
    return root;
}
 
 
    /* Driver program to test lca() */
    public static void main(String args[])
    {
        // Let us construct the BST shown in the above figure
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(20);
        tree.root.left = new Node(8);
        tree.root.right = new Node(22);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(12);
        tree.root.left.right.left = new Node(10);
        tree.root.left.right.right = new Node(14);
 
        int n1 = 10, n2 = 14;
        Node t = tree.lca(tree.root, n1, n2);
        System.out.println("LCA of " + n1 + " and " + n2 + " is " + t.data);
 
        n1 = 14;
        n2 = 8;
        t = tree.lca(tree.root, n1, n2);
        System.out.println("LCA of " + n1 + " and " + n2 + " is " + t.data);
 
        n1 = 10;
        n2 = 22;
        t = tree.lca(tree.root, n1, n2);
        System.out.println("LCA of " + n1 + " and " + n2 + " is " + t.data);
 
    }
}

Output

LCA of 10 and 14 is 12 
LCA of 14 and 8 is 8 
LCA of 10 and 22 is 20 

Complexity Analysis: 

• Time Complexity: O(h). 
  The Time Complexity of the above solution is O(h), where h is the height of the tree.
• Space Complexity: O(1). 
  The space complexity of the above solution is constant.