Print All The Nodes At Distance From The Target Node

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
2 upvotes
Asked in companies
Urban Company (UrbanClap)MAQ Software

Problem statement

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.

alt text

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.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer ‘T’ denoting the number of test cases.
The next ‘2*T’ lines represent the ‘T’ test cases.

The first line of input contains two space-separated integers, the first denotes the given target node’s value and the second denotes the ‘K’.

The second line of input contains the elements of the tree in the level order form separated by a single space.
If any node does not have a left or right child, take -1 in its place. Refer to the example below.

Example:

Elements are in the level order form. The input consists of values of nodes separated by a single space in a single line. In case a node is null, we take -1 in its place.

For example, the input for the tree depicted in the below image would be :

alt text

 1
 2 3
 4 -1 5 6
-1 7 -1 -1 -1 -1
-1 -1

Explanation :
Level 1 :
The root node of the tree is 1

Level 2 :
Left child of 1 = 2
Right child of 1 = 3

Level 3 :
Left child of 2 = 4
Right child of 2 = null (-1)
Left child of 3 = 5
Right child of 3 = 6

Level 4 :
Left child of 4 = null (-1)
Right child of 4 = 7
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 6 = null (-1)
Right child of 6 = null (-1)

Level 5 :
Left child of 7 = null (-1)
Right child of 7 = null (-1)

The first not-null node (of the previous level) is treated as the 
parent of the first two nodes of the current level. The second not- 
null node (of the previous level) is treated as the parent node for 
the next two nodes of the current level and so on.

The input ends when all nodes at the last level are null (-1).
Note : 
The above format was just to provide clarity on how the input is 
formed for a given tree. 

The sequence will be put together in a single line separated by a 
single space. Hence, for the above-depicted tree, the input will be 
given as:

1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1
Output Format: 
For every test case, return a list/vector of the node’s value that 
are at distance ‘K’ from the given target node’s value.
Note 
You are not required to print anything; it has already been taken care of. Just implement the function and return the answer.
Constraint : 
1 <= T <= 10^2
1 <= N <= 3*10^3
1 <= K <= 12
-10^9 <= data <= 10^9

Where ‘T’ represents the number of test cases, ‘N’ is the number of nodes in the tree, ‘K’ is an integer that denotes the distance of the node from the target node and ‘data’ denotes data contained in the node of a binary tree.

Time Limit: 1 sec
Sample Input 1:
2
4 3
1 2 3 4 5 -1 -1 -1 -1 6 -1 -1 -1
3 1
1 2 3 -1 -1 4 5 -1 -1 -1 -1
Sample output 1:
3 6
1 4 5
Explanation For Sample Input 1:
Test case 1:

alt text

Given the target node’s value is ‘4’.
All the nodes that are at distance ‘3’ from the given target node ( ‘4’ ):

4-> 2-> 5-> 6 node ( ‘6’ )
4-> 2-> 1-> 3 node ( ‘3’)
Hence there are ‘2’ nodes that are at distance ‘3’ from the node ( ‘4’). Return a list/vector ‘{ 6, 3 }’


Test case 2:

alt text

Given the target node’s value is ‘3’.
All the nodes that are at distance ‘1’ from the given target node ( ‘3’ ):

3-> 4 node ( ‘4’ )
3-> 5 node ( ‘5’ )
3-> 1 node ( ‘1’ )
Hence there are ‘3’ nodes that are at distance ‘1’  from the node ( ‘3’ ). Return a list/vector ‘{ 4, 5, 1 }’.
Sample Input 2:
2
2 2
1 2 3 -1 -1 -1 -1
6 3
1 2 3 4 5 -1 -1 6 -1 -1 -1 -1 -1
Sample output 2:
3
1 5
Hint

Try to use recursion

Approaches (2)
Recursion

Suppose from the current node, if the target node is at depth ‘X’ in the left subtree. So that nodes at distance ‘K-X’ in the right subtree should be part of the answer array and it is ‘K’ distance from the given target node. Go to ROOT→LEFT, now target node is at depth ‘X-1’ from the CURRENTNODE(ROOT->LEFT), then find all the nodes that are ‘K - X + 1’ depth and all should be added to the answer.

 

  1. Two types of nodes are possible that are at distance ‘K’ from the target node -
    • Part of target node subtree.
    • Part of any other ancestor of the target node.
  2. Traverse every node of a given binary tree with help of depth-first search ( ‘DFS’ ). And assume that ‘DFS( CURRENTNODE )’ returns the distance of ‘CURRENTNODE’ from the target node.
  3. There can be 4 cases -
    • currentNode is target or 'CURRENTNODE == TARGETNODE’ :
      • Then add all the nodes that are at distance ‘K’ from ‘CURRENTNODE’ and subtree part of ‘CURRENTNODE/TARGET’ node.
      • Call the ADDNODE function with ‘ADDNODE( CURRNODE, 0)’
        • ‘ADDNODE( DUMMYNODE, X )’ function adds all the node’s values in the ‘ANSWER’ array/vector which is at distance ‘K - X’ from ‘DUMMYNODE’.
  4. The target node is part of the left subtree of ‘CURRENTNODE’ :
    • Call ‘DFS( CURRENTNODE -> LEFT)’
      • It returns two types of value.
    • Any integer value ‘X’ except ‘-1’, ‘X’ is the depth of the target node from the ‘CURRENTNODE’ and target node in the left subtree of ‘CURRENTNODE’.
      • If ‘X’ is equal to ‘K’ then add ‘CURRENTNODE’ in the ‘ANSWER’ array.
      • Call the ‘ADDNODE( CURRENTNODE→RIGHT, X )’
    • If the return value is ‘-1’, that’s mean the target node is not a part of CURRENTNODE'S left subtree.
  5. The target node is part of the right subtree of ‘CURRENTNODE’ :
    • Call ‘DFS( CURRENTNODE -> RIGT )’
      • It returns two types of value as same as a left call of ‘CURRENTNODE’.
    • Any integer value ‘X’ except ‘-1’, ‘X’ is the depth of the target node from the ‘CURRENTNODE’ and target node in the right subtree of ‘CURRENTNODE’.
      • If ‘X’ is equal to ‘K’ then add ‘CURRENTNODE’ in the ‘ANSWER’ array.
      • Call the ‘ADDNODE( CURRENTNODE->LEFT, X )’.
    • If the return value is ‘-1’, that’s mean the target node is not a part of CURRENTNODE'S right subtree.
  6. The target node is not a part of CURRENTNODE'S subtree.
    • Stop recursion and return.
  7. Return ‘ANSWER’ array/vector.
Time Complexity

O(N), Where ‘N’ is the number of nodes in a binary tree.

 

We are traversing every node at max twice.

Space Complexity

O(N), Where ‘N’ is the number of nodes in a binary tree.

 

In the recursive function, the recursion call stack can have at max 'N' nodes stored here. hence the space complexity will be O(N).

Code Solution
(100% EXP penalty)
Print All The Nodes At Distance From The Target Node
Full screen
Console