Leftmost and rightmost nodes in a binary tree

Easy
0/40
Average time to solve is 20m
0 upvote
Asked in companies
SAP LabsGrabDisney + Hotstar

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
1
1 2 3 4 5 6 7 -1 -1 -1 -1 -1 -1 -1 -1
Sample Output 1:
1 1
2 3 
4 7
Explanation for sample input 1:

alt text

Sample Input 2:
1
1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1
Sample Output 2:
1 1
2 3
4 6
7 7
Hint 
Use Hashing to store the nodes at a particular level.
Approaches (2)
Hashing

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

  1. 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.
  2. 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.
  3. 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].

Time Complexity

O(N), where N is the number of nodes in the tree.

Space Complexity

O(N), where N is the number of nodes in the tree. We are using extra space in the form of a hashmap. Also, we require extra space for the stack used in recursive calls.

Code Solution
(100% EXP penalty)
Leftmost and rightmost nodes in a binary tree
Full screen
Console