Last Updated: 2 Dec, 2020

Deepest Left

Moderate
Asked in companies
UberFreshworks

Problem statement

You are given a binary tree having ‘N’ number of nodes. Your task is to find the deepest leaf node in the given input tree.

Note:

The deepest leaf node is the leaf node which will be the left child of some node and will be at the maximum level in the tree.
If there are multiple deepest left leaf nodes, return the node with maximum value.

Note :

1. A binary tree is a tree in which each node can have at most two children. 
2. The given tree will be non-empty i.e. the number of non-NULL nodes will always be greater than or equal to 1.
3. Multiple nodes in the tree can have the same values, all values in the tree will be positive.

Input format :

The first line of input contains an integer ‘T’, which denotes the number of test cases. Then each test case follows. 
The first line of every test case contains elements of the Binary Tree in the level order form. The input consists of values of nodes separated by a single space in a single line. In case a node is null, we take -1 in its place.

For Example :

Consider the binary tree:


The input for the tree depicted in the above image would be :

3
5 1
6 2 0 8
-1 -1 7 4 -1 -1 -1 -1
-1 -1 -1 -1

Explanation :

Level 1 :
The root node of the tree is 3

Level 2 :
Left child of 3 = 5
Right child of 3 = 1

Level 3 :
Left child of 5 = 6
Right child of 5 = 2
Left child of 1 = 0
Right child of 1 = 8

Level 4 :
Left child of 6 = null (-1)
Right child of 6 = null(-1)
Left child of 2 = 7
Right child of 2 = 4
Left child of 0 = null (-1)
Right child of 0 = null (-1)
Left child of 8 = null (-1)
Right child of 8 = null (-1)

Level 5 :
Left child of 7 = null (-1)
Right child of 7 = null (-1)
Left child of 4 = null (-1)
Right child of 4 = 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 deepest leaf node’s data which is the left child of some node.

The output of each test case should be printed 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 <= 5
1 <= N <= 3 * (10 ^ 3)
1 <= nodeVal <= 10 ^ 9

Time Limit: 1 sec.

Approaches

01 Approach

The idea is to traverse the tree iteratively and whenever a left tree node is pushed into the queue, check if it is a leaf node, if it’s a leaf node, then update the result. Since we go level by level, the last stored leaf node is the deepest one.

 

Approach:

 

  • First, check if the root is null or not.
  • Make a queue for breadth-first search.
  • Initialize a variable of int type say ‘result’ to 0, ‘maxLevel’ to 0, ‘level’ to 1.
  • Push the root inside the queue.
  • Make an iteration till the queue does not become empty.
    • Store the size of the queue in a variable, say ‘si’.
    • Iterate till size does not become 0.
      • Store the queue’s front element in a variable, say ‘temp’, and pop the element from the queue.
      • Check if there existed the left element of ‘temp’ in the tree or not.
        • If a left element of ‘temp’ exists:
          • Push temp’s left into the queue.
          • If temp’s left node is the leaf node then:
            • Check if temp’s left level is greater than the ‘maxLevel’ then store the temp’s left’s data in the variable ‘result’ and update ‘maxLevel with the level of temp’s left’s level.
            • Else, if temp’s left’s level is already reached level then store the maximum element in ‘result’
        • If a right element of ‘temp’ exists:
          • Push temp’s right into the queue.
    • Increment ‘level’.
    • Update ‘maxLevel’.
  • Return ‘result’ to the function.

02 Approach

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

 

Approach :

 

  • First make a recursive function say, ‘Solve()’ taking root, ‘level’ representing the current level of the tree, boolean variable ‘isLeft’ representing whether the current node is a left child or not, ‘maxLevel’ to store the maximum level in the tree, and ‘ans’ to store the deepest left node’s data.
  • Check if the root is null or not.
  • Recursively call the function, ‘Solve()’ for the left subtree by incrementing ‘level’ and making ‘isLeft’ as true.
  • Now check if the current node is a leaf node and the left child of some node.
    • If ‘maxLevel’ < ‘level’ then update ‘maxVal’ and store root’s data in ‘ans’.
    • Else if ‘maxLevel’ == ‘level’ then store maximum value in ‘ans’.
  • Similarly, call the function ‘Solve()’ recursively for the right subtree by incrementing ‘level’ and making ‘isLeft’ as false.