Last Updated: 7 Oct, 2020
Deepest Right Leaf
Moderate
Asked in companies
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:
Output: 9
Explanation: The deepest right nodes are 3 and 9 but 9 is the rightmost, thus 9 is the answer.
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
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
Approaches
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:
- 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.
- Also, initialize a static node variable ‘RESULT’ which will store the value of the nodes at the deepest right level.
- 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.
- In the helper function, the base case would be if the root is ‘NULL’, then return.
- 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’.
- Recur for the left and right subtree of the tree.
- Finally, return the ‘RESULT’.
Traverse the tree level by level and while pushing the right child to queue, check if it is a leaf node, if it’s a leaf node, then update the result and since we are traversing level by level, the last stored right leaf will be the deepest right leaf node.
Step involved:
- If the ‘ROOT’ is null/none return null/none.
- Create a queue of Nodes and push the ‘ROOT’ node into it.
- Initialize a node variable ‘RESULT’ to null, where ‘RESULT’ will store the deepest right leaf node of the Binary Tree at the end.
- Run a loop while the queue is not empty:
- Pop the front node from the queue.
- If the left node of the popped node is not ‘NULL’ then push the left node into the queue.
- If the right node of the popped node is not ‘NULL’ then push the right node into the queue and check if the right node is the leaf node or not, if it is, then updates the ‘RESULT’ with the right node.
- Finally, return the result.