- Given a binary tree, find least or lowest common ancestor (LCA) of two given nodes.
- Given input nodes should exists in a binary tree.
- We will use depth first search (DFS) recursive algorithm to traverse the binary tree.
- We have discussed the similar problem Find LCA in BST
Example of least common ancestor nodes is:
We will analyse the Fig 1 binary tree and find out the LCA of nodes lying in different subtrees.
| S. No. | Input nodes | LCA |
|---|---|---|
| 1 | LCA (F , G) | C |
| 2 | LCA ( C, G) | C |
| 3 | LCA (D ,E ) | B |
| 4 | LCA (D ,B ) | B |
| 5 | LCA (D, C ) | A |
| 6 | LCA (E ,G ) | A |
Example 1: LCA of Node B (25) & C (75) of a binary tree. (Fig 2).
- Perform depth first search traversal.
- Traverse left subtree of Node A & We will find node B (input node).
- Node B will send its reference to its parent (Node A).
- Traverse right subtree of Node A & We will find node C (input node).
- Node C will send its reference to its parent (Node A)
- Node A getting non null from its left and right subtree.
- Node A will be LCA of Node B & Node C
Example 2: LCA of Node B (25) and D (10) of a binary tree. (Fig 3).
- Perform DFS traversal of binary tree.
- Traverse the left subtree of Node A.
- We found Node B (whose LCA we would like to find).
- No need to traverse underlying nodes).
- return node B to its parent node A.
- Traverse the right subtree of Node A.
- In right subtree traversal (Node C), we will not get node B or D.
- Right subtree will return null to its parent node A.
- Node A will get node B from left subtree & null from right subtree.
- Non null value i.e. Node B will be LCA of Node B & Node D.
Example 3: LCA of Node I & Node K (refer Fig 4).
- Perform DFS traversal of binary tree to find LCA of Node I & K
- Traverse left subtree of node A ie Node B
- Traverse left subtree of Node B i.e. Node D
- Right subtree traversal of Node D will find Node I.
- Node D will return reference of Node I to Node B.
- Traverse right subtree of Node B i.e. Node E
- Right subtree traversal of Node E will find Node K.
- Node D will return reference of Node K to Node B.
- Node B got node I from left subtree and Node K from right subtree
- return Node B to its parent i.e. Node A.
- Traverse left subtree of Node B i.e. Node D
- Traverse right subtree of Node A i.e. Node C.
- Traverse left & right subtrees of Node C
- No match will be found & return null to Node A.
- Node A will get Node B from left subtree & null from right subtree.
- Node B will LCA of Node I & Node K.
Example 4: LCA of Node I and Node M (refer Fig 5).
We can analyse the Fig 5 similar to previous examples.
Time complexity of algorithm is O(n).
Program to find lowest common ancestor of input nodes.
1.) LCA Class: LCA class is responsible for finding lowest common ancestors of two input nodes in a given binary tree.
package org.learn.Question;public class LCA { public static Node lca(Node root, Node node1, Node node2) { if (null == root) { return root; } if (root == node1 || root == node2) { return root; } Node left = lca(root.left, node1, node2); Node right = lca(root.right, node1, node2); if (left != null && right != null) { return root; } if (left != null) return left; else return right; }} |
2.) Node Class: Node class is representing the nodes of a given binary tree.
package org.learn.Question;public class Node { public int data; public Node left; public Node right; public Node(int num) { this.data = num; this.left = null; this.right = null; } public Node() { this.left = null; this.right = null; } public static Node createNode(int number) { return new Node(number); }} |
3.) App Class: We are creating the binary tree in a main method & calling method of LCA class to find least or lowest common ancestor of two input nodes of a given binary tree.
package org.learn.Client;import org.learn.Question.LCA;import org.learn.Question.Node;public class App { public static void main(String[] args) { // root level 0 Node A = Node.createNode(50); // Level 1 Node B = Node.createNode(25); Node C = Node.createNode(75); // Level 2 Node D = Node.createNode(15); Node E = Node.createNode(40); Node F = Node.createNode(60); Node G = Node.createNode(95); // Level 3 Node H = Node.createNode(10); Node I = Node.createNode(20); Node J = Node.createNode(30); Node K = Node.createNode(45); Node L = Node.createNode(55); Node M = Node.createNode(65); // connect Level 0 and 1 A.left = B; A.right = C; // connect level 1 and level 2 B.left = D; B.right = E; C.left = F; C.right = G; // connect level 2 and level 3 D.left = H; D.right = I; E.left = J; E.right = K; F.left = L; F.right = M; Node lca = LCA.lca(A, D, H); String message = String.format("1. LCA[Node D (%d) & Node H (%d)] = %d", D.data,H.data,lca.data); System.out.println(message); lca = LCA.lca(A, I, K); message = String.format("2. LCA[Node I (%d) & Node K (%d)] = %d", I.data, K.data, lca.data); System.out.println(message); lca = LCA.lca(A, I, M); message = String.format("3. LCA[Node I (%d) & Node M (%d)] = %d", I.data, M.data, lca.data); System.out.println(message); }} |
Output: Least common ancestors of input nodes :
1. LCA[Node D (15) & Node H (10)] = 152. LCA[Node I (20) & Node K (45)] = 253. LCA[Node I (20) & Node M (65)] = 50 |