lowest common ancestor of a binary search tree

June 23, 2019

Following is definition of LCA from Wikipedia:
Let T be a rooted tree. The lowest common ancestor between two nodes n1 and n2 is defined as the lowest node in T that has both n1 and n2 as descendants (where we allow a node to be a descendant of itself).

Thus lca is guaranteed to exist if both the nodes are present in tree. In any other case it is NULL.

LCA of 4 and 5 is 3.
LCA of 2 and 5 is 1.
LCA of 3 and 5 is 3.

To find LCA , The below code assumes that both the nodes are present in the tree. To extend this algo for the cases that , it works even if only one of nodes are present in the tree, is left as an exercise to the reader. There are 2 ways to do this – One is to check beforehand if the nodes are present in the tree or not. Other way to change our solution a bit to account to check if both the nodes are present. Like 2 variables which update when we find the nodes in finding LCA.

//Java implementation to find lowest common ancestor of
// n1 and n2 using one traversal of binary tree

/* Class containing left and right child of current
node and key value*/
class Node {
    int data;
    Node left, right;

    public Node(int item) {
        data = item;
        left = right = null;
    }
    public Node() {
        data = 0;
        left = right = null;
    }
}

public class BTree {

    Node root;



    // This function returns pointer to LCA of two given
    // values n1 and n2. This function assumes that n1 and
    // n2 are present in Binary Tree
    Node LCA(Node node, int val1, int val2) {
        // Base case
        if (node == null)
            return null;

        // If either n1 or n2 matches with root's key, return root. Note this assumes that
        // both thr roots are present in the tree. To extend this algo for those cases , which
        //account if either of the node is present or not, is Left as an exercise for students.
        if (node.data == val1 || node.data == val2)
            return node;

        // Look for keys in left and right subtrees
        Node left_lca = LCA(node.left, val1, val2);
        Node right_lca = LCA(node.right, val1, val2);

        // If both the left_lca and right_lca is not null, that means this is LCA.
        if (left_lca != null && right_lca != null)
            return node;

        // Otherwise check if left subtree or right subtree is LCA
        if (left_lca != null)
            return left_lca;
        else
            return right_lca;

    }
    public static void main(String args[]) {
        BTree tree = new BTree();
        tree.root = new Node(11);
        tree.root.left = new Node(9);
        tree.root.right = new Node(8);
        tree.root.left.left = new Node(7);
        tree.root.left.right = new Node(6);
        tree.root.right.left = new Node(5);
        tree.root.right.right = new Node(4);
        System.out.println("LCA(9, 8) = " +
            tree.LCA(tree.root, 9, 8).data);

        System.out.println("LCA(11, 4) = " +
            tree.LCA(tree.root, 11, 4).data);

    }
}