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.
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.
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.
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
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).
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.
You do not need to print anything, it has already been taken care of. Just implement the given function.
1 <= T <= 5
1 <= N <= 3 * (10 ^ 3)
1 <= nodeVal <= 10 ^ 9
Time Limit: 1 sec.
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.
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.
Preorder Traversal
Preorder Traversal
Inorder Traversal
Inorder Traversal
Inorder Traversal
Inorder Traversal
Inorder Traversal
Postorder Traversal
Postorder Traversal
Height of Binary Tree
Height of Binary Tree
Height of Binary Tree
Height of Binary Tree
Locked Binary Tree