Last Updated: 16 Dec, 2020

Print All The Nodes At Distance From The Target Node

Moderate

Asked in companies

Solve now

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.

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

Solve now

Approaches

01 Approach

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.

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.
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.
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’.
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.
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.
The target node is not a part of CURRENTNODE'S subtree.
- Stop recursion and return.
Return ‘ANSWER’ array/vector.

Solve now

02 Approach

The basic idea of this approach is that, if we have a parent node of every node then we can find all the nodes at depth ‘K’ in any direction.

Create parent pointer of every node -
- Implement the ‘DFS’ based recursive function in which we add a ‘PAR’ pointer to every node and a ‘PAR’ pointer will be pointed to the parent’s node.
- Suppose current node is ‘curNode’ then call DFS( CURNODE→LEFT, CURNODE) and in the next step we will convert ‘CURNODE→PAR= CURNODE’.
- Now ‘CURNODE→PAR’ points to the parent node.
- Same step for the ‘RIGHT’ child.
Now each node is pointing to its ‘LEFT’ child, ‘RIGHT’ child, and parent node.
Apply the breadth-first search( 'BFS' ) from the ‘TARGET’ node and add all the nodes that are ‘K’ distance from the target node.
Call the ‘BFS’ function exactly for the ‘K’ level, then we reach at depth ‘K’ from the target node and add the all nodes into the answer array that are present at “K’th” level and return ‘ANSWER’ array.
- BFS( CURNODE -> LEFT)
- BFS( CURNODE -> RIGHT)
- BFS( CURNODE -> PAR)
Let's consider a case -
- CURNODE -> LEFT=> LEFTCHILDNODE
- LEFTCHILDNODE -> PAR => CURNODE
- Suppose we are at the current node and call ‘LEFT’ subtree, in the second step we are at the ‘LEFT’ child of the current node and we call the parent node and we reach again at current node.
- It means, due to the presence of a child and parent pointer we can count one node twice. So we need a ‘SEEN’ map in which we store the current node visited or not. If the current node is visited then return back else traverse its parent or child node.

Solve now