Find Nodes at Distance K in a Binary Tree
Your task is to find all nodes that are exactly a distance K from a given node in an arbitrary binary tree. The distance is defined as the number of edges between nodes.
Input:
The first line contains an integer T, the number of test cases. For each test case: 1. The tree's nodes are given in level order (use -1 for a NULL node). 2. The value of the target node is specified. 3. An integer K represents the required distance from the target node.
Output:
For each test case, output a list of node values that are exactly K edges away from the given target node. If no such nodes exist, return an empty list.
Example:
Input:
1
3 5 1 6 2 0 8 -1 -1 7 4 -1 -1 -1 -1 -1 -1 -1 -1
target = 5
K = 2
Output:
[7, 4, 0, 8]
Constraints:
1 ≤ T ≤ 100
1 ≤ N ≤ 3000
0 ≤ K ≤ 3000
0 ≤ nodeValue ≤ 3000
Note:
- The binary tree is non-empty and can contain nodes with the same value. - If there are multiple nodes fulfilling the distance requirement, their order in the output list does not matter.
Be the first one to answer
Add answer anonymously...
Top Microsoft Corporation SDE-2 interview questions & answers
Popular interview questions of SDE-2
Top HR questions asked in Microsoft Corporation SDE-2
>
Microsoft Corporation SDE-2 Interview Questions
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