











lowest common ancestor of a binary search tree
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); } }
Login/Signup to comment