Deepest left leaf node in a binary tree | A C ++ program to find the deepest left leaf in a given binary tree ; A Binary Tree node ; New node ; A utility function to find deepest leaf node . lvl : level of current node . maxlvl : pointer to the deepest left leaf node found so far isLeft : A bool indicate that this node is left child of its parent resPtr : Pointer to the result ; Base case ; Update result if this node is left leaf and its level is more than the maxl level of the current result ; Recur for left and right subtrees ; A wrapper over deepestLeftLeafUtil ( ) . ; Driver program to test above function
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int val ; struct Node * left , * right ; } ; Node * newNode ( int data ) { Node * temp = new Node ; temp -> val = data ; temp -> left = temp -> right = NULL ; return temp ; } void deepestLeftLeafUtil ( Node * root , int lvl , int * maxlvl , bool isLeft , Node * * resPtr ) { if ( root == NULL ) return ; if ( isLeft && ! root -> left && ! root -> right && lvl > * maxlvl ) { * resPtr = root ; * maxlvl = lvl ; return ; } deepestLeftLeafUtil ( root -> left , lvl + 1 , maxlvl , true , resPtr ) ; deepestLeftLeafUtil ( root -> right , lvl + 1 , maxlvl , false , resPtr ) ; } Node * deepestLeftLeaf ( Node * root ) { int maxlevel = 0 ; Node * result = NULL ; deepestLeftLeafUtil ( root , 0 , & maxlevel , false , & result ) ; return result ; } int main ( ) { Node * root = newNode ( 1 ) ; root -> left = newNode ( 2 ) ; root -> right = newNode ( 3 ) ; root -> left -> left = newNode ( 4 ) ; root -> right -> left = newNode ( 5 ) ; root -> right -> right = newNode ( 6 ) ; root -> right -> left -> right = newNode ( 7 ) ; root -> right -> right -> right = newNode ( 8 ) ; root -> right -> left -> right -> left = newNode ( 9 ) ; root -> right -> right -> right -> right = newNode ( 10 ) ; Node * result = deepestLeftLeaf ( root ) ; if ( result ) cout << " The ▁ deepest ▁ left ▁ child ▁ is ▁ " << result -> val ; else cout << " There ▁ is ▁ no ▁ left ▁ leaf ▁ in ▁ the ▁ given ▁ tree " ; return 0 ; }