Find Shortest Path in a Tree
Given a tree with 'N' nodes and 'N - 1' distinct edges, along with two nodes 'N1' and 'N2', find and print the shortest path between 'N1' and 'N2'.
Explanation:
A tree is a nonlinear hierarchical data structure composed of nodes connected by edges. It has no cycles, all node values are unique, and the nodes 'N1' and 'N2' always exist in the tree.
Input:
The first line of input contains an integer 'T' denoting the number of test cases. Each test case consists of two parts:
1. The first part is the tree represented in level order format: ROOT_DATA, 'N' (number of children), followed by 'N' children, repeated for every node.
2. The second part contains two space-separated integers 'N1' and 'N2'.
Output:
For each test case, output a single line showing the shortest path from 'N1' to 'N2'.
Example:
Input:
T = 1
Tree = 20 2 10 35 2 5 15 2 30 42 0 1 13 0 0 0
N1, N2 = 15 35
Output:
15 10 20 35
Constraints:
- 1 <= T <= 10^2
- 1 <= N <= 25 * 10^2
- 1 <= NODE_DATA <= 10^5
- 1 <= N1, N2 <= 10^5
Time Limit: 1 second
Note:
You do not need to print anything; it has already been taken care of. Just implement the given function.
AnswerBot
8d
Find the shortest path between two nodes in a tree.
Use Breadth First Search (BFS) algorithm to find the shortest path in a tree.
Start BFS from one of the nodes and keep track of the parent of each nod...read more
Help your peers!
Add answer anonymously...
Top Samsung Software Developer Intern interview questions & answers
Popular interview questions of Software Developer Intern
Stay ahead in your career. Get AmbitionBox app
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+
Reviews
4 L+
Interviews
4 Cr+
Salaries
1 Cr+
Users/Month
Contribute to help millions
Get AmbitionBox app