Find the Deepest Node in a Binary Tree | A Python3 program to find value of the deepest node in a given binary tree by method 3 ; A tree node with constructor ; constructor ; Funtion to return the deepest node ; Creating a Queue ; Iterates untill queue become empty ; Driver Code
from collections import deque NEW_LINE class new_Node : NEW_LINE INDENT def __init__ ( self , key ) : NEW_LINE INDENT self . data = key NEW_LINE self . left = self . right = None NEW_LINE DEDENT DEDENT def deepestNode ( root ) : NEW_LINE INDENT node = None NEW_LINE if root == None : NEW_LINE INDENT return 0 NEW_LINE DEDENT q = deque ( ) NEW_LINE q . append ( root ) NEW_LINE while len ( q ) != 0 : NEW_LINE INDENT node = q . popleft ( ) NEW_LINE if node . left is not None : NEW_LINE INDENT q . append ( node . left ) NEW_LINE DEDENT if node . right is not None : NEW_LINE INDENT q . append ( node . right ) NEW_LINE DEDENT DEDENT return node . data NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = new_Node ( 1 ) NEW_LINE root . left = new_Node ( 2 ) NEW_LINE root . right = new_Node ( 3 ) NEW_LINE root . left . left = new_Node ( 4 ) NEW_LINE root . right . left = new_Node ( 5 ) NEW_LINE root . right . right = new_Node ( 6 ) NEW_LINE root . right . left . right = new_Node ( 7 ) NEW_LINE root . right . right . right = new_Node ( 8 ) NEW_LINE root . right . left . right . left = new_Node ( 9 ) NEW_LINE levels = deepestNode ( root ) NEW_LINE print ( levels ) NEW_LINE DEDENT