Find the Deepest Node in a Binary Tree | A Binary Tree Node Utility function to create a new tree node ; maxLevel : keeps track of maximum level seen so far . res : Value of deepest node so far . level : Level of root ; Update level and resue ; Returns value of deepest node ; Initialze result and max level ; Updates value " res " and " maxLevel " Note that res and maxLen are passed by reference . ; Driver Code
class newNode : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . data = data NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE self . visited = False NEW_LINE DEDENT DEDENT def find ( root , level , maxLevel , res ) : NEW_LINE INDENT if ( root != None ) : NEW_LINE INDENT level += 1 NEW_LINE find ( root . left , level , maxLevel , res ) NEW_LINE if ( level > maxLevel [ 0 ] ) : NEW_LINE INDENT res [ 0 ] = root . data NEW_LINE maxLevel [ 0 ] = level NEW_LINE DEDENT find ( root . right , level , maxLevel , res ) NEW_LINE DEDENT DEDENT def deepestNode ( root ) : NEW_LINE INDENT res = [ - 1 ] NEW_LINE maxLevel = [ - 1 ] NEW_LINE find ( root , 0 , maxLevel , res ) NEW_LINE return res [ 0 ] NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = newNode ( 1 ) NEW_LINE root . left = newNode ( 2 ) NEW_LINE root . right = newNode ( 3 ) NEW_LINE root . left . left = newNode ( 4 ) NEW_LINE root . right . left = newNode ( 5 ) NEW_LINE root . right . right = newNode ( 6 ) NEW_LINE root . right . left . right = newNode ( 7 ) NEW_LINE root . right . right . right = newNode ( 8 ) NEW_LINE root . right . left . right . left = newNode ( 9 ) NEW_LINE print ( deepestNode ( root ) ) NEW_LINE DEDENT