Python program to find deepest left leaf node in a binary tree using recursion














































Python program to find deepest left leaf node in a binary tree using recursion



DESCRIPTION: The idea is to recursively traverse the given binary tree and while traversing, maintain %u201Clevel%u201D which will store the current node%u2019s level in the tree. If the current node is left leaf, then check if its level is more than the level of 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 the maximum of the two depths.

CODE::

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


Comments