Find Path

Hard
0/120
Average time to solve is 10m
profile
Contributed by
6 upvotes
Asked in companies
CoinbaseMorgan StanleySamsung

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
3
1 0
1 1
1 2 2 3 0 1 4 0
1 2
1 1 2 1 3 1 4 0
1 3
Sample Output 1:
1
1 2
1 2 3
Explanation For Sample Input 1:
(i) Since there is only one node from node- 1 to node 1 so, we print only 1 as the path.
(ii) Since 1 and 2 are directly connected so, we print 1 2 as the path.
(iii) Going from 1 to 3 we have 2 as the child of 1 and 3 as the child of 2. Hence the path is 1 2 3.
Sample Input 2:
3
1 2 2 3 2 4 5 2 6 7 0 0 0 0 
1 5
1 1 2 1 3 0
2 3
1 1 2 2 3 4 2 5 6  2 7 8 0 0 0 0 
1 8
Sample Output 2:
1 2 5
2 3
1 2 4 8
Explanation For Sample Input 2:
(i) Going from 1 to 5 we have 2 as the child of 1 and 4 and 5 as the child of 2. Hence the path is 1 2 5.

example

(ii) Since 2 and 3 are directly connected so, we print 2 3 as the path.

example

(iii) Going from 1 to 8 we have 2 as the child of 1, 3 and 4 as the child of 2 and 7 and 8 as the child of 4. Hence the path is 1 2 4 8.

example

Hint

Try to think of how you can find a node that is ancestor to both nodes and use this node to get path.

Approaches (2)
Brute Force

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

 

  1. Define PATH1 And PATH2 as an empty ArrayList.
  2. 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:

 

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

 

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

 

  1. Find ELEMENTOFINTERSECTION between PATH1 and PATH2.
  2. Return PATH1 from PATH1.size()-1 to ELEMENTOFINTERSECTION.
  3. Return PATH2 from ELEMENTOFINTERSECTION to PATH2.size()-1.
Time Complexity

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

Space Complexity

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.

Code Solution
(100% EXP penalty)
Find Path
Full screen
Console