If you want to practice data structure and algorithm programs, you can go through 100+ data structure and algorithm programs.

In this post, we will see about Lowest Common Ancestor for n-ary Tree.

## Problem

Given a n-ary tree also known as a Generic Tree and also two nodes. You need to find the Lowest common ancestor of the two given nodes.

A n**-ary tree** is basically a tree with any number of children.

**Lowest Common Ancestor** is the node which is the common ancestor for both the nodes which is closest to them or we can say, farthest from root.

Consider the Given Tree,

**Input Format:**

In the first line, given n, the number of nodes, following that n-1 lines contains two integers, the first one representing parent, second one is the child.

After that, given two Integers, whose LCA is to be found.

For Eg:-

18

1 2

1 3

1 4

2 5

2 6

3 7

4 8

4 9

4 10

5 11

11 12

11 13

7 14

7 15

15 16

15 17

15 18

6 13

Output : 2

## Solution

**Approach – I :**

In this approach, we will basically use the find node algorithm, we start with root node, keep searching for both of the given nodes whose **LCA** id to be found say**(u, v)**.

- There are two cases When a node will be LCA :
- (i) When itself is one of the node i.e equal to u or v, and other node falls in the subtree of its children.
- (ii) When both the nodes falls in the DIFFERENT subtrees of its children, if they fall in the

same subtree of its child, then this node might not be the LCA.

- So we start from root node, keep on recurring in preorder, searching for u and v. If we find any node of u and v then we return true, as this might be the LCA, even though we have a different condition for considering it as the LCA which we will see later.
- When we recur for children of any node, we keep a counter of how many child are giving a true as result, because :
- (i) If exactly Two of its children return true, this means that the current node is the LCA (As discussed in the second case).
- (ii) If one of its child return true and it itself is one of the node whose LCA to be found then this node is LCA (As discussed in the First case).

As we are setting LCA in postorder, we need to make sure that we set it only once.

As we are recurring in preorder, visiting every node, so the time complexity of this approach would be **O(n)**.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 |
package org.arpit.java2blog; import java.util.ArrayList; import java.util.Scanner; public class LCAnFind { public static void main(String[] args) { Scanner scn = new Scanner(System.in); int numNodes = scn.nextInt(); @SuppressWarnings("unchecked") ArrayList<Integer>[] tree = new ArrayList[numNodes + 1]; for (int i = 0; i < tree.length; i++) { tree[i] = new ArrayList<>(); } // for a tree, edges are always equal to nodes-1 as it does not // have any cycle. int edges = numNodes - 1; while (edges-- > 0) { int parent = scn.nextInt(); int child = scn.nextInt(); tree[parent].add(child); } getLCA(1, tree, scn.nextInt(), scn.nextInt()); System.out.println("Output: "+lca); } static int lca = -1; public static boolean getLCA(int node, ArrayList<Integer>[] tree, int u, int v) { /* if current node is equal to one of the nodes whose lca we are finding, then it is a potential candidate for being the lca. */ boolean self = node == u || node == v ? true : false; int count = 0; /* recurring for every child. and keeping a count of result of how many times we are getting true. */ for (int child : tree[node]) { if (getLCA(child, tree, u, v)) { count++; } } /* this is the main check, if current node itself is one of the node whose lca is to be found and its getting true from any of its child, then surely it is LCA of given nodes. also, if we get true from exactly two sides, this means that current node is the node after which the path for both nodes diverge, and hence it is the LCA for given nodes. */ if (((self && count == 1) || (count == 2))) { /* lca will be set only once, as the parent of lca will have the count==2 condition as true, but that is not the correct answer. */ if (lca == -1) { lca = node; } return true; } /* current node will return true only if either the current node is one of the given nodes, or one of its children return true for count == 2, we already handled it while setting LCA. */ return self || count == 1; } } |

**Approach – II :**

This approach also solves the give problem in linear time i.e with the worst time complexity of **O(n)**.

We basically use **Root to node path** to find out the LCA of two nodes.

* Lets first discuss how we find root to node path :

- We keep on traversing the tree in preorder basically looking for the node whose path we are currently finding.
- Once we find the node, there is no need for further calls for siblings or for child, we will return true and for stopping those further calls, we check if we already got a true already, if yes, then this means that we already found the node.
- We add the node into our path and while backtracking in postorder, we add only one node at a level, because if we keep adding the nodes in postorder without any check, then it is more likely that we will also add the sibling for a node whose root to node path we are actually finding.
- Now after we got our root to node path, we will traverse both the paths starting from extreme right end for both, and keep moving until we get a different node on both pointers, this means that the node which we are currently at is the node at which the path for both given nodes(whose LCA is to be found) are diverged and hence the previous node is the LCA of both nodes.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 |
package org.arpit.java2blog; import java.util.ArrayList; import java.util.HashMap; import java.util.Scanner; public class LCAnRTNP { public static class Node { int val; // as its a K-ary tree, So we make a variable array to store its children. ArrayList<Integer> children = new ArrayList<>(); // constructor,initializing the node value and public Node(int val) { this.val = val; this.children = new ArrayList<>(); } } static HashMap<Integer, Node> nodeMap = new HashMap<>(); static Node root; public static void main(String[] args) { Scanner scn = new Scanner(System.in); int numnodes = scn.nextInt(); for (int i = 0; i <= numnodes; i++) { nodeMap.put(i, new Node(i)); } root = nodeMap.get(1); int edges = numnodes - 1; while (edges-- > 0) { int parent = scn.nextInt(); int child = scn.nextInt(); // storing child in the arraylist of the parent. ArrayList<Integer> children = nodeMap.get(parent).children; children.add(child); } getLCA(scn.nextInt(), scn.nextInt()); } public static void getLCA(int node1, int node2) { // root to node path for node1 ArrayList<Integer> path1 = new ArrayList<>(); rootToNodePath(root, path1, nodeMap.get(node1)); path1.add(root.val); // root to node path for node2 ArrayList<Integer> path2 = new ArrayList<>(); rootToNodePath(root, path2, nodeMap.get(node2)); path2.add(root.val); System.out.println(path1 + "\n" + path2); int p1 = path1.size() - 1; int p2 = path2.size() - 1; int prevMatchingNode = -1; /* * We start two pointers for two paths i.e. one for each node. * we will start from extreme right, keep moving both * pointers towards left until we get a different value * on both pointers this is the node where the path for node1 * and node2 diverges, and hence, the previous node is the * lCA for node1 and node 2. */ while (p1 >= 0 && p2 >= 0) { if (path1.get(p1) == path2.get(p2)) { prevMatchingNode = path1.get(p1); p1--; p2--; } else { break; } } System.out.println("Output: "+prevMatchingNode); } public static boolean rootToNodePath(Node node, ArrayList<Integer> path, Node nodeToFind) { if (node.val == nodeToFind.val) { return true; } boolean res = false; boolean addedInPath = false; for (int val : node.children) { /* * this or operator plays a very crutial role here * as while backtracking in postorder, we dont want * to again visit every node. instead, we want to go * straight back to the immediate parent rather than * exploring its siblings. */ res = res || rootToNodePath(nodeMap.get(val), path, nodeToFind); if (res && !addedInPath) { path.add(val); addedInPath = true; /* also we need to keep track that at any particular level * we want only one node to be added into * our root to node path.*/ } } return res; } } |

When you run above program, you will get below output:

1 2

1 3

1 4

2 5

2 6

3 7

4 8

4 9

4 10

5 11

11 12

11 13

7 14

7 15

15 16

15 17

15 18

6 13

[6, 2, 1]

[13, 11, 5, 2, 1]

Output: 2

That’s all about Lowest Common Ancestor for any K-ary Tree