SDE - 1

Given a binary tree, a target node in the binary tree, and an integer ‘K’. You need to find all the nodes that are at a distance ‘K’ from the given target node.

No parent node pointer is available.

Example -

In the below binary tree, suppose the given target node value is 2 and ‘K’ is 2.

There  are 3 node’s that are at distance ‘2’ from node value ‘2’:
2-> 5 -> 7  node( 7 )
2-> 5 -> 8  node( 8 )
2-> 1 -> 3  node( 3 )

Hence we return an array of all three node’s value that are at distance ‘2’ from the given target node’s value ‘2’ = ‘{ 7, 8, 3 }’.

Note:

1)  You can return the list/vector in any order of the node’s value.

2) If there is no node that is at distance ‘K’ from the given target node then return an empty list/vector.

There were three different glasses and unlimited water. Can you fill the third glass using the first two glasses if you don’t have anything to measure with?

Design ATM.