Lowest Common Ancestor of a Binary Search Tree
Lowest Common Ancestor
On this page we will se how to find Lowest Common Ancestor of a Binary Search 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.
Sum of all Nodes in a Binary Tree
Algorithm :
- Create a recursive function that takes a node, as well as two values n1 and n2.
- If the value of the current node is less than both n1 and n2, it means that the lowest common ancestor (LCA) lies in the right subtree. Call the recursive function for the right subtree.
- If the value of the current node is greater than both n1 and n2, it means that the LCA lies in the left subtree. Call the recursive function for the left subtree.
- If both of the above cases are false, it means that the current node is the LCA. Return the current node as the LCA.
To find LCA , The below code assumes that both the nodes are present in the tree. To extend this algorithm 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.
Code to find Lowest Common Ancestor in a binary tree in Java
//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; } } 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 class Main{ 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); } }
Output
LCA(9, 8) = 11 LCA(11, 4) = 11
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Introduction to Trees
Binary Trees
- Binary Tree in Data Structures (Introduction)
- Tree Traversals: Inorder Postorder Preorder : C | C++ | Java
- Inorder Postorder PreOrder Traversals Examples
- Tree Traversal without Recursion
Binary Search Trees
Traversals
- Traversal in Trees
- Tree Traversals: Breadth-First Search (BFS) : C | C++ | Java
- Tree Traversals: Depth First Search (DFS) : C | C++ | Java
- Construct a Binary Tree from Postorder and Inorder
B – Trees
AVL Trees
- AVL Trees
Complete Programs for Trees
- Depth First Traversals – C | C++ | Java
- Level Order Traversal – C | C++ | Java
- Construct Tree from given Inorder and Preorder traversals – C | C++ | Java
- Construct Tree from given Postorder and Inorder traversals – C | C++ | Java
- Construct Tree from given Postorder and Preorder traversal – C | C++ | Java
- Find size of the Binary tree – C | C++ | Java
- Find the height of binary tree – C | C++ | Java
- Find maximum in binary tree – C | C++ | Java
- Check whether two tree are identical- C| C++| Java
- Spiral Order traversal of Tree- C | C++| Java
- Level Order Traversal Line by Line – C | C++| Java
- Hand shaking lemma and some Impotant Tree Properties.
- Check If binary tree if Foldable or not.- C| C++| Java
- check whether tree is Symmetric – C| C++| Java.
- Check for Children-Sum in Binary Tree- C|C++| Java
- Sum of all nodes in Binary Tree- C | C++ | Java
- Lowest Common Ancestor in Binary Tree- C | C++ | Java
Introduction to Trees
Binary Trees
- Binary Tree in Data Structures (Introduction)
- Tree Traversals: Inorder Postorder Preorder : C | C++ | Java
- Inorder Postorder PreOrder Traversals Examples
- Tree Traversal without Recursion
Binary Search Trees
Traversals
- Traversal in Trees
- Tree Traversals: Breadth-First Search (BFS) : C | C++ | Java
- Tree Traversals: Depth First Search (DFS) : C | C++ | Java
- Construct a Binary Tree from Postorder and Inorder
B – Trees
AVL Trees
- AVL Trees
Complete Programs for Trees
- Depth First Traversals – C | C++ | Java
- Level Order Traversal – C | C++ | Java
- Construct Tree from given Inorder and Preorder traversals – C | C++ | Java
- Construct Tree from given Postorder and Inorder traversals – C | C++ | Java
- Construct Tree from given Postorder and Preorder traversal – C | C++ | Java
- Find size of the Binary tree – C | C++ | Java
- Find the height of binary tree – C | C++ | Java
- Find maximum in binary tree – C | C++ | Java
- Check whether two tree are identical- C| C++| Java
- Spiral Order traversal of Tree- C | C++| Java
- Level Order Traversal LIne by Line – C | C++| Java
- Hand shaking lemma and some Impotant Tree Properties.
- Check If binary tree if Foldable or not.- C| C++| Java
- check whether tree is Symmetric C| C++| Java.
- Check for Children-Sum in Binary Tree- C|C++| Java
- Sum of all nodes in Binary Tree- C | C++ | Java
- Lowest Common Ancestor in Binary Tree. C | C++ | Java