How to Find Lowest Common Ancestor of a Binary Tree in Java? Example Tutorial

Hello guys, if you are wondering how to find the lowest common ancestor of a binary tree in Java then you are at the right place. Earlier, I have shared 40+ binary tree questions and today I am going to share solution of one of the popular binary tree question here. To find the lowest common ancestor of a binary tree in java requires that we run through a binary search tree and how it operates.  What then is a binary search tree? A Binary tree is a data structure in which each node can have at most two children. That is, each node in the binary tree will have data, left child and right child. The first node of the tree is called the Root.

Below is the image of the Binary search tree, the first circle with 15 is called the root node and it has two children, left and right nodes with the values,10 and 20 respectively. Node 10 has two children too with 5 and 13 as values. The left child of node 10 does not have any child but, the right node with value 13 has two children nodes 12 and 14 respectively.

Fig 1.0: Finding the lowest common ancestor.

There are some important things to note when determining is if a tree is a binary tree or not, which are :

 All data in the nodes of the left sub-tree are lesser than the right.

 In the Children nodes, all data on the left are lesser than the right.

 All data in the nodes of the left sub-tree is lesser than the root

 All data in the nodes of the right sub-tree is greater than the root.

 So, with all these bullet points you can determine if a tree is a binary tree or not.

Now, before looking into codes what do we mean by the lowest common ancestor? Let’s see.

The lowest common ancestor is defined between two nodes n1 and n2 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). 

Or we can say The lowest common Ancestor (LCA) of two nodes and in a rooted tree is the lowest (deepest) node that is an ancestor of both and remember that an ancestor of a node in a rooted tree is any node that lies on the path from the root to (including).

Note the following:

· All of the node’s values will be unique.

· node1 and node2 are different and both values will exist in the binary tree.

· You can use extra memory, helper functions, and can modify the node structure but, you can’t add a parent pointer.

Java Program to find the Lowest Common Ancestor of a Binary Tree

We would be looking at how to find the lowest common ancestor of a binary search tree in java. I'm sure the picture above communicates something about the problem we are about to solve. Let's check some codes!

1. public class LowestCommonAncestor {
2. static class Node {
3. int data;
4. Node left, right;
5. public Node(int data) {
6. this.data = data;
7. left = right = null;
8. }
9. }
10. public static int LCA(Node root, int n1, int n2) {
11. if (root == null) {
12. return -1;
13. }
14. Node current= root;
15. int lca = -1;
16. while (current != null) {
17. if (current.data < n1 && current.data < n2) {
18. // LCA is present in the right sub tree
19. current = current.right;
20. } else if (current.data > n1 &¤t.data > n2) {
21. // LCA is present in left sub tree
22. current = current.left;
23. } else {
24. lca = current.data;
25. break;
26. }
27. }
28. return lca;
29. }
30. public static void main(String[] args) {
31. LowestCommonAncestor.Node root = new LowestCommonAncestor.Node(20);
32. root.left = new LowestCommonAncestor.Node(11);
33. root.right = new LowestCommonAncestor.Node(24);
34. root.right.left = new LowestCommonAncestor.Node(21);
35. root.right.right = new LowestCommonAncestor.Node(35);
36. root.right.right.left = new LowestCommonAncestor.Node(32);
37. root.right.right.right = new LowestCommonAncestor.Node(40);
38. System.out.println(LCA(root, 24, 40));
39. System.out.println(LCA(root, 11, 21));
40. System.out.println(LCA(root, 32, 40));
41. }
42. }

OUTPUT:

24

20

35

Line 1 was the class declaration with an embedded Node class with instance variables: data of type int, right, and left of type node respectively. Constructor was declared in line 5 that takes in parameter “data” of type int and was assigned to the instance variable in line 6. In line 7, right was assigned to left, and null was assigned to the right. 

In other words, it means left is null. The method LCA was declared in line 10 with three parameters which are the root of type node, int n1, and n2 respectively. If the root is null then it should return -1 in line 12. 

Line 14 stored the root parameter into the variable "current" of the type node. Variable "lca" of type int was set to -1 too. 

So, from line 17, inasmuch as the root is not null it would proceed to check if the data in the current node is less than n1 and n2 and if so current.right is assigned to current(which means  "lca" is present in the right sub-tree) else, if the data in the current node is greater than n1 and n2, current.left is assigned to current(which means  "lca" is present in the left sub-tree). 

But if the two conditions are not met. Variable "lca" should still hold current.data. Line 25 breaks the loop and "lca" was returned in line 28

The main method starts from line 30 and line 31 created the instance of the “LowestCommonAncestor” class, with the value of 20 as the root.

Line 32 to line 37 were adding data to the nodes as specified from the root whether left or right. Line 38,39 and 40 called the method “LCA” respectively and was printed out.

 Other Coding Interview Questions  you may like

• How to apply Bucket Sort in Java? (tutorial)
• How to implement Quicksort algorithm without recursion? (tutorial)
• How to perform a Binary Search Algorithm in Java? (tutorial)
• How to implement the insertion sort algorithm in Java? (tutorial)
• How to find the most significant and smallest number in an array without sorting? (solution)
• How to find duplicates from an unsorted array in Java? (solution)
• How to apply the Quicksort algorithm in place in Java? (tutorial)
• How to implement the Bubble sort algorithm in Java? (tutorial)
• Difference between Comparison and Non-Comparison based sorting algorithm? (answer)
• How to find all pairs in an array whose sum is equal to k (solution)
• How to remove duplicates from an array in Java? (solution)
• How to find one missing number in a sorted array? (solution)
• How to find a missing value from an array containing 1 to 100? (solution)
• 50+ Data Structure and Algorithms Problems from Interviews (questions)
• My favorite free courses to learn data Structure in-depth (FreeCodeCamp)
• How to remove an element from an array in Java? (solution)
• How to check if an array contains a particular value? (solution)
• 10 Free Data Structure and Algorithm Courses for Programmers (courses)
• 100+ Data Structure Coding Problems from Interviews (questions)

Thanks for reading this article. If you like this article, then please share it with your friends and colleagues. If you have any questions or feedback, then please drop a note.