Last Updated: 18 Dec, 2020

Leftmost and rightmost nodes in a binary tree

Easy

Asked in companies

Solve now

Problem statement

You are given an arbitrary binary tree with N nodes, whose nodes have their values in the range of integers. You have to print the values of leftmost and rightmost nodes at each level of the given tree. In other words, for every level in the given tree, print the values of corner nodes.

Two nodes are said to be at the same level if they are at the same distance from the root node.

Note:

1. For all such levels where there is only one corner node the leftmost and the rightmost nodes are the same.
2. In the output, you have to print the leftmost and rightmost values in level order fashion i.e, the leftmost node of level1 followed by the rightmost node of level1 followed by the leftmost node of level2 followed by the rightmost node of level2 and so on.

Input Format:

The first line of the input contains a single integer T, representing the number of test cases.

The first and only line of each test case contains the values of the nodes of the tree in the level order form ( -1 for NULL node) 

Refer to the example for further clarification.

Example:

Consider the binary tree

alt text

The input of the tree shown in the above image will look like: 
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).

Output Format:

For each test case, print the values of leftmost and rightmost nodes at each level, separated by a single space in a separate line.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 50
1 <= N <= 10^4
-10^9 <= nodeVal <= 10^9
Time Limit: 1sec

Solve now

Approaches

01 Approach

We can create a HashMap of the form (key->level_number, value->list of nodes at level=level_number) by doing inorder traversal of the array. Then, traverse through this map and print the first and last values of the arrays corresponding to each key in the map. For this recursion, the base condition will occur when the node is NULL.

Algorithm

Create an empty hashmap where the key will be level_number and its value will be an array which represents the nodes at that level_number.
To fill the map, do an inorder traversal of the given queue. In the recursive function, we pass the current node, its level in an integer variable called ‘level’ and the hashmap ‘map’ to be filled. The hashmap will be passed by reference. Make a recursive call to the left child of the current node, with level+1. Append current node’s value to the array corresponding to map[level] and then make a recursive call for the right child, with level+1.
Once the hashmap is ready, we can simply get the leftmost and rightmost nodes of any level, say x by accessing map[x][0] and map[x][map[x].size()-1] respectively.

To understand the algorithm clearly, let us take the binary tree given in sample input 1 above.

Create a hashmap map<int, vector<int>> to store the levels of the tree. Initialize a temporary variable level=0 and pass the map, level and root into an auxiliary function which will traverse the given tree in an inorder manner and also fill the hashmap with corresponding values. At every recursive call, we increment the value of level.

The hashmap for the given example will look like:-

0→ {1}

1→ {2, 3}

2→ {4, 5, 6, 7}

Now, coming back to our original function, we traverse the filled map and print the first and last values at each level using map[level][0] and map[level][map[level].size()-1].

Solve now

02 Approach

The first thing that comes to mind after reading this problem is that we need to move in a level order fashion, hence we can use BFS traversal to solve this problem. We create a queue to store the nodes and keep track of the nodes at a particular level. At every iteration, we store the size of the queue in a temporary variable, say size. Now all we need to do is to run a loop from i=0 to size-1 and print the front of the queue when i=0 and i=size-1. Also, we keep pushing the left and right children of the nodes being popped from the queue to traverse all the next level in the tree.

Algorithm

Create a queue and push the root node in it.
While the queue is non-empty,
Store the size of the queue in an integer variable called ‘size’.
Run a loop from i=0 to size-1. Remove the front element of the queue and store it in ‘front’. For i=0, the front of the queue will be the the leftmost node at current level and for i=size-1, the front of the queue will be the rightmost node at current level. Hence, print the front node’s value when i=0 or i=size-1. Also, push the left and right child of the ‘front’ in the queue.

3. Terminate.

Solve now