Last Updated: 21 Nov, 2020
Find Path
Hard
Asked in companies
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 <= T <= 10^2
1 <= N <= 25 * 10^2
1 <= NODE_DATA <= 10^5
1 <= N1, N2<= 10^5
Time Limit: 1 second
Approaches
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.
- If HASPATH for ROOT to N1 and HASPATH for ROOT to N2 are both true:
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.
- If HASPATH for CHILD, PATH and X is true:
- 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.
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.
- If HASPATH for LCANODE to N1 and HASPATH for LCANODE to N2 are both true:
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.
- If HASPATH for CHILD, PATH and X is true:
- 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.
Similar problems