Nodes at Distance K from a Given Node

Given an arbitrary binary tree, a specified node within the tree, and an integer 'K', find all nodes that are exactly 'K' distance away from the specified node. Return a list of these node values.

Explanation:

The distance between two nodes in a binary tree is defined by the number of edges connecting them.

Input:

The initial line contains an integer T, indicating the number of test cases.
The first line of each test case presents the values of the tree nodes in level order, using -1 to signify a NULL node.
The second line specifies the target node value.
The third line gives the integer K, which indicates the distance for locating nodes.

Output:

For each test case, return the values of all nodes at a distance K from the given node.

Example:

Input:
3
5 1
6 2 0 8
-1 -1 7 4 -1 -1 -1 -1
-1 -1 -1 -1
Output:
[List of values at K distance]

Constraints:

  • 1 ≤ T ≤ 100
  • 1 ≤ N ≤ 3000
  • 0 ≤ K ≤ 3000
  • 0 ≤ nodeValue ≤ 3000

Note:

  • A binary tree allows each node to have at most two children.
  • The tree is non-empty and can contain nodes with identical values.
  • If no nodes are found at the specified distance, return an empty list.
  • The order of node values in the returned list does not matter.
AnswerBot
4d

Find all nodes at a specified distance K from a given node in a binary tree.

  • Traverse the binary tree to find the target node.

  • Use depth-first search to explore nodes at distance K from the target node....read more

Help your peers!
Add answer anonymously...
Josh Technology Group 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