Lowest Common Ancestor (LCA) for n-ary Tree

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,
LCA n-ary 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:-

Input :
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).

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 :

  1. We keep on traversing the tree in preorder basically looking for the node whose path we are currently finding.
  2. 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.
  3. 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.
  4. 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.

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

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
[6, 2, 1]
[13, 11, 5, 2, 1]
Output: 2

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


import_contacts

You may also like:

Related Posts

  • 29 November

    Top 100+ Java coding interview questions

    I have been posting data structure and coding interview questions on various topics such as Array, Queue, Stack, Binary tree, LinkedList, String, Number, ArrayList, etc. So I am consolidating a list of java coding interview questions to create an index post. I will keep adding links to this post whenever I will add new java […]

  • 18 April

    Minimum Number of Jumps to reach last Index

    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 how to find Minimum Number of Jumps to reach last Index. Problem Given an array A of positive integers possibly zeroes, every index indicating the maximum length of a […]

  • 28 March

    Sort an array of 0s, 1s and 2s

    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 how to sort an array of 0s, 1s and 2s.We have already seen a post on sort 0s and 1s in an array. Problem Given an array containing zeroes, […]

  • 04 March

    Check if it is possible to reach end of given Array by Jumping

    If you want to practice data structure and algorithm programs, you can go through 100+ data structure and algorithm programs.   Problem Given an array with positive integers as elements indicating the maximum length of a jump which can be made from any position in the array. Check if it is possible to have […]

  • 17 February

    Check if Array Elements are Consecutive

    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 how to check if array elements are consecutive. Problem Given an array, we need to check if array contains consecutive elements. For example: Input: array[] = {5, 3, 4, […]

  • 04 February

    LCA of a K-ary Tree in O(Sqrt(height))

    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 how to find Lowest Common Ancestor of a K-ary Tree in O(Sqrt(height)).We have already seen how to find LCA of n-ary tree in O(n) complexity. Problem Given a […]

Leave a Reply

Your email address will not be published. Required fields are marked *

Subscribe to our newletter

Get quality tutorials to your inbox. Subscribe now.