Last Updated: 7 Dec, 2020

Nodes Vertically Below Root Node

Moderate

Asked in company

Solve now

Problem statement

King Greg’s kingdom is divided like a binary tree such that the capital of the empire was in the North, and all the remaining cities are below the capital city. One day King Greg wanted to know all the cities which are in the South(Vertically below) of the capital city, But Greg is too busy managing his kingdom, so you have to help Greg find all the cities vertically below the capital city.

If there is no node vertically below the root node, return -1.

For Example :

In this tree, cities 5 and 6 are directly below the capital city; hence, the answer is 5, 6.

Input format :

The first line contains a single integer ‘T’ denoting the number of test cases to be run. Then the test cases follow.

The first line of each test case contains the elements of the binary 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.

1
2 3
-1 4 -1 -1
5 -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 = null (-1)
Right child of 2 = 4
Left child of 3 = null (-1)
Right child of 3 = null (-1)

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

Level 5 :
Left child of 5 = null (-1)
Right child of 5 = 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 -1 4 -1 -1 5 -1 -1 -1

Output format :

For each test case, return a List containing all the cities vertically below the root node.

Output for each test case will be printed in a separate line.

Note :

 You are not required to print anything; it has already been taken care of. Just implement the function and return the answer.

Constraints :

1 <= T <= 100
1 <= N <= 3000
0 <= NodeVal <= 10^9

Time Limit: 1sec

Solve now

Approaches

01 Approach

So the approach is we have to traverse through the tree, from both left and right sides, until we reach the leaf node and keep a variable ‘Distance’ which will calculate how far is the current node from the root node, if ‘Distance’ is zero we push that node into list ‘Ans’.

The steps are as follows:

For the ‘Recursion’ Function:
1. If ‘Distance’ equals zero then push node->Data to the list ‘Ans’.
2. If the current node has a left child then call ‘Recursion’ for the left child of the current node, and decrease Distance by 1. Recursion(node->Left, Distance - 1).
3. If the current node has a right child then call ‘Recursion’ for the right child of the current node, and increase Distance by 1. Recursion(node->Right, Distance + 1).

In the given Function:
1. Take a list ‘Ans’ for storing the final answer and a variable ‘Distance’ for storing the distance of a node from the root node.
2. Call the function ‘Recursion’ for the left and right node of the Root node, and pass the Distance variable -1 and 1 for the left side and right side, respectively.
3. Return the list ‘Ans’.

Solve now