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...
Samsung Software Developer Intern Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
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

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter