Deepest Right Leaf

Moderate
0/80
Average time to solve is 20m
12 upvotes
Asked in companies
WalmartExpedia GroupNavyug Infosolutions Pvt. Ltd.

Problem statement

You have been given a Binary Tree of 'N' nodes. Your task is to find and return the deepest right leaf node. In case of multiple answers, return the rightmost node.

For example: 
For the given binary tree:

alt-text

Output: 9

Explanation: The deepest right nodes are 3 and 9 but 9 is the rightmost, thus 9 is the answer.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The only line of the input contains elements in the level order form. The line consists of values of nodes separated by a single space. In case a node is null, we take -1 in its place.
Example: 
The input for the tree depicted in the below image would be : 
1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1

alt text

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)

1
2 3
4 -1 5 6
-1 7 -1 -1 -1 -1
-1 -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.
Note : 
1. The above format was just to provide clarity on how the input is formed for a given tree. 

2. The input ends when all nodes at the last level are null (-1).
Output Format: 
The only line of output will contain an integer representing the deepest right leaf node of the given binary tree.
Note: 
You don't need to print the output, it has already been taken care of. Just implement the given function.
Constraints: 
0 <= N <= 10^5
0 <= data <= 10^5

Where 'N' denotes the number of nodes in the Binary Tree and 'data' represents the node value of the nodes in the Binary Tree.

Time limit: 1 sec
Sample Input 1:
1 2 3 -1 -1 -1 -1
Sample Output 1:
3
Explanation to Sample Output 1:
The input binary tree will be represented as:

alt-text

From the above representation, the leaves node are 2 and 3. But 3 is the right child of its parent but 2 is the left child of its parent. Thus, 3 should be the answer.
Sample Input 2:
1 2 3 -1 4 4 -1 -1 5 6 -1 -1 -1 -1 -1
Sample Output 2:
5
Explanation to Sample Output 2:
The input binary tree will be represented as:

alt-text

From the above representation, the leaves node are 5 and 6. But 5 is the right child of its parent but 6 is the left child of its parent. Thus, 5 should be the answer.
Hint

Try to think of a recursive approach.

Approaches (2)
Recursive Approach

The idea here is to traverse the given binary tree and while traversing, maintain a ‘LEVEL’ which will store the current node’s level in the tree. If the current node is a left node, then check if its level is more than the level of the deepest right leaf seen so far. If the level is more, then update the result. If the current node is not the leaf node, then recursively find maximum depth in left and right subtrees, and return the maximum of the two depths.

 

Steps that will be used:

 

  1. Initialize an integer variable ‘LEVEL’ to 0 and a static integer variable ‘MAXDEPTH’ to 0, where the ‘LEVEL’ will store the depth of the current node and ‘MAXDEPTH’ will store the deepest right leaf node seen so far.
  2. Also, initialize a static node variable ‘RESULT’ which will store the value of the nodes at the deepest right level.
  3. Call a helper function of void return type having parameters definition (NODE, ‘LEVEL’, ‘MAXDEPTH’, ‘ISRIGHT’) and initial parameters would be (root, 0, ‘maxDepth’, false), where ‘ISRIGHT’ checks whether the node is a right child of the parent or not.
  4. In the helper function, the base case would be if the root is ‘NULL’, then return.
  5. Check if the current node is the leaf node and right child of its parent and its level is more than ‘MAXDEPTH’ then the current node would be the deepest right leaf node seen so far, thus updating the ‘MAXDEPTH’ and ‘RESULT’.
  6. Recur for the left and right subtree of the tree.
  7. Finally, return the ‘RESULT’.
Time Complexity

O(N), where ‘N’ is the total number of nodes in the given binary tree.

 

Since we will be traversing each node only once in O(N) time, the total time complexity will be O(N).

Space Complexity

O(N), where ‘N’ is the total number of nodes in the given binary tree.

 

Since in the worst case every node of the Binary Tree will be in the recursion stack and takes O(N) space. Thus the total space complexity will be O(N).

Code Solution
(100% EXP penalty)
Deepest Right Leaf
Full screen
Console