Find Path
You are given a tree with 'N' nodes with 'N' - 1 distinct edge. You are also given two nodes 'N1' and 'N2'. You have to find and print the shortest path between 'N1' and 'N2'.

A tree data structure is a nonlinear hierarchical data structure that consists of nodes connected by edges.

Note

1. There is no cycle present in a tree. 2. All values in the tree are unique. 3. Both nodes will always exist in the tree.

Input format

The first line of input contains an integer 'T' representing the number of the test case. Then the test case follows. The first line of each test case contains elements of a tree in level order form separated by space. Order is: ROOT_DATA, 'N' (Number of children of the root), 'N' children, and so on for every element The second line of each test case contains two space-separated integers 'N1' and 'N2'. For example, the input for the tree depicted in the below image would be :

Explanation :

Level 1 : The root node of the tree is 20 Level 2 : 1st child of 20 = 10 2nd child of 20 = 35 Level 3 : 1st child of 10 = 5 2nd child of 10 = 15 1st child of 35 = 30 2nd child of 35 = 42 Level 4 : Children of 5 = 0 Ist child of 15 = 13 Children of 30 = 0 Children of 42 = 0 Level 5 : Children of 13 = 0 The input ends when all nodes at the last level have 0 children. Note: A tree node may have zero or more child nodes. The above format was just to provide clarity on how the input is formed for a given tree. The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as: 20 2 10 35 2 5 15 2 30 42 0 1 13 0 0 0

Output Format

For each test case, print the shortest path from 'N1' to 'N2' in a single line. The output of each test case will be printed in a separate line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1

Question

Find Path

You are given a tree with 'N' nodes with 'N' - 1 distinct edge. You are also given two nodes 'N1' and 'N2'. You have to find and print the shortest path between 'N1' and 'N2'.

A tree data structure is a nonlinear hierarchical data structure that consists of nodes connected by edges.

Note

1. There is no cycle present in a tree.
2. All values in the tree are unique.
3. Both nodes will always exist in the tree.

Input format

The first line of input contains an integer 'T' representing the number of the test case. Then the test case follows.

The first line of each test case contains elements of a tree in level order form separated by space. 

Order is:
ROOT_DATA, 'N' (Number of children of the root), 'N' children, and so on for every element 

The second line of each test case contains two space-separated integers 'N1' and 'N2'.

For example, the input for the tree depicted in the below image would be :

example

Explanation :

Level 1 :
The root node of the tree is 20

Level 2 :
1st child of 20 = 10
2nd child of 20 = 35

Level 3 :
1st child of 10 = 5
2nd  child of 10 = 15
1st child of 35 = 30
2nd child of 35 = 42

Level 4 :
Children of 5 = 0
Ist child of 15 = 13
Children of 30 = 0
Children of 42 = 0

Level 5 :
Children of 13 = 0

The input ends when all nodes at the last level have 0 children.

Note:
A tree node may have zero or more child nodes.
The above format was just to provide clarity on how the input is formed for a given tree. 
The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:
20 2 10 35 2 5 15 2 30 42 0 1 13 0 0 0

Output Format

For each test case, print the shortest path from 'N1' to 'N2' in a single line.

The output of each test case will be printed in a separate line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10^2
1 <= N <= 25 * 10^2
1 <= NODE_DATA <= 10^5
1 <= N1, N2<= 10^5

Time Limit: 1 second

Accepted Answer

Tip 1 : I used graph traversal with an array
:

Accepted Answer

Brute Force

Consider function FINDPATH that takes ROOT node, node N1 and node N2 as parameter and:

Define PATH1 And PATH2 as an empty ArrayList.
Check and store path from ROOT to N1 in PATH1 and from ROOT to N2 in PATH2 by using function HASPATH:
- If HASPATH for ROOT to N1 and HASPATH for ROOT to N2 are both true:
  - Call function PRINTPATH for PATH1 and PATH2.
- Else print NO PATH.

We define function HASPATH that accepts tree node ROOT, array list of integers PATH and integer X as parameters and:

Check if ROOT is NULL, return FALSE.
Add ROOT.DATA to PATH.
If ROOT.DATA is equal to X, return TRUE.
Initialize a boolean variable PATHEXIST as FALSE.
Iterate for ROOT.CHILDREN and check:
- If HASPATH for CHILD, PATH and X is true:
  - Assign TRUE to PATHEXIST.
  - Return PATHEXIST.
Remove PATH(PATH.SIZE()-1).
Return PATHEXIST.

We define function PRINTPATH that accepts array list of integers PATH1 and PATH2 as parameters and:

Find ELEMENTOFINTERSECTION between PATH1 and PATH2.
Return PATH1 from PATH1.size()-1 to ELEMENTOFINTERSECTION.
Return PATH2 from ELEMENTOFINTERSECTION to PATH2.size()-1.

Space Complexity: O(n)Explanation:

O(N) where N is the number of nodes in the tree.

The space complexity of the algorithm is O(N) because we are using extra arrays to store the path and also because of recursion stack space in memory.

Time Complexity: O(n)Explanation:

O(N) where N is the number of nodes in the tree.

We are finding the path between two nodes which will take linear time because in the worst case we have to visit all nodes of the tree to check if it is in the path or not. Hence the time complexity of the algorithm will be O(N).

Accepted Answer

Lowest Common Ancestor

Consider function FINDPATH that takes ROOT node, node N1 and node N2 as parameters and:

Define PATH1 And PATH2 as an empty ArrayList.
Find LCANODE by calling function FINDLCA for ROOT, N1 and N2.
Check and store path from LCANODE to N1 in PATH1 and from LCANODE to N2 in PATH2 by using function HASPATH:
- If HASPATH for LCANODE to N1 and HASPATH for LCANODE to N2 are both true:
  - Call function PRINTPATH for PATH1 and PATH2.
- Else print NO PATH.

We define function HASPATH that accepts tree node ROOT, array list of integers PATH and integer X as parameters and:

Check if ROOT is NULL, return FALSE.
Add ROOT.DATA to PATH.
If ROOT.DATA is equal to X, return TRUE.
Initialize a boolean variable PATHEXIST as FALSE.
Iterate for ROOT.CHILDREN and check:
- If HASPATH for CHILD, PATH and X is true:
  - Assign TRUE to PATHEXIST.
  - Return PATHEXIST.
Remove PATH(PATH.SIZE()-1).
Return PATHEXIST.

We define function PRINTPATH that accepts array list of integers PATH1 and PATH2 as parameters and:

Print PATH1 from PATH1.size()-1 to 0.
Print PATH2 from 1 to PATH2.size()-1.

We define function FINDLCA that takes ROOT node, node N1 and node N2 as parameters and:

Check if ROOT is NULL, return FALSE
Check if ROOT.data is the same as N1 and N2 both:
- Assign ROOT to LCANODE and return TRUE.
Initialize boolean variable SELF to TRUE if ROOT.data is same as either N1 or N2, else false.
Initialize COUNT to 0
Iterate for ROOT.CHILDREN and for each CHILD:
- Call FINDLCA function for CHILD, N1 and N2, and if it is TRUE increment COUNT by 1.
If SELF is TRUE and COUNT is 1 or if COUNT is 2, check:
- if LCANODE is NULL, assign ROOT to LCANODE.
- Return TRUE
Return TRUE if SELF is true or COUNT is 1.

Space Complexity: O(1)Explanation:

O(N) where N is the number of nodes in the tree.

The space complexity of the algorithm is O(N) because of recursion stack space in memory.

Time Complexity: O(n)Explanation:

O(N) where N is the number of nodes in the tree.

We are finding the path between two nodes which will take linear time because in the worst case we have to visit all nodes of the tree to check if it is in the path or not. Hence the time complexity of the algorithm will be O(N).

You are given a tree with 'N' nodes with 'N' - 1 distinct edge. You are also given two nodes 'N1' and 'N2'. You have to find and print the shortest path between 'N1' and 'N2'.

A tree data structure is a nonlinear hierarchical data structure that consists of nodes connected by edges.

Note

Input format

Explanation :

Output Format

Note:

Constraints:

Top Morgan Stanley Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Morgan Stanley Software Developer