Deepest left leaf node in a binary tree | A binary tree node ; Constructor to create a 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 max level of the current result ; Recur for left and right subtrees ; A wrapper for left and right subtree ; Driver program to test above function
class Node : NEW_LINE INDENT def __init__ ( self , val ) : NEW_LINE INDENT self . val = val NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def deepestLeftLeafUtil ( root , lvl , maxlvl , isLeft ) : NEW_LINE INDENT if root is None : NEW_LINE INDENT return NEW_LINE DEDENT if ( isLeft is True ) : NEW_LINE INDENT if ( root . left == None and root . right == None ) : NEW_LINE INDENT if lvl > maxlvl [ 0 ] : NEW_LINE INDENT deepestLeftLeafUtil . resPtr = root NEW_LINE maxlvl [ 0 ] = lvl NEW_LINE return NEW_LINE DEDENT DEDENT DEDENT deepestLeftLeafUtil ( root . left , lvl + 1 , maxlvl , True ) NEW_LINE deepestLeftLeafUtil ( root . right , lvl + 1 , maxlvl , False ) NEW_LINE DEDENT def deepestLeftLeaf ( root ) : NEW_LINE INDENT maxlvl = [ 0 ] NEW_LINE deepestLeftLeafUtil . resPtr = None NEW_LINE deepestLeftLeafUtil ( root , 0 , maxlvl , False ) NEW_LINE return deepestLeftLeafUtil . resPtr NEW_LINE DEDENT root = Node ( 1 ) NEW_LINE root . left = Node ( 2 ) NEW_LINE root . right = Node ( 3 ) NEW_LINE root . left . left = Node ( 4 ) NEW_LINE root . right . left = Node ( 5 ) NEW_LINE root . right . right = Node ( 6 ) NEW_LINE root . right . left . right = Node ( 7 ) NEW_LINE root . right . right . right = Node ( 8 ) NEW_LINE root . right . left . right . left = Node ( 9 ) NEW_LINE root . right . right . right . right = Node ( 10 ) NEW_LINE result = deepestLeftLeaf ( root ) NEW_LINE if result is None : NEW_LINE INDENT print " There ▁ is ▁ not ▁ left ▁ leaf ▁ in ▁ the ▁ given ▁ tree " NEW_LINE DEDENT else : NEW_LINE INDENT print " The ▁ deepst ▁ left ▁ child ▁ is " , result . val NEW_LINE DEDENT