Deepest right leaf node in a binary tree | Iterative approach | Helper function that allocates a new node with the given data and None left and right poers . ; Constructor to create a new node ; utility function to return level of given node ; create a queue for level order traversal ; traverse until the queue is empty ; Since we go level by level , the last stored right leaf node is deepest one ; Driver Code ; create a binary tree
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 DEDENT DEDENT def getDeepestRightLeafNode ( root ) : NEW_LINE INDENT if ( not root ) : NEW_LINE INDENT return None NEW_LINE DEDENT q = [ ] NEW_LINE q . append ( root ) NEW_LINE result = None NEW_LINE while ( len ( q ) ) : NEW_LINE INDENT temp = q [ 0 ] NEW_LINE q . pop ( 0 ) NEW_LINE if ( temp . left ) : NEW_LINE INDENT q . append ( temp . left ) NEW_LINE DEDENT if ( temp . right ) : NEW_LINE INDENT q . append ( temp . right ) NEW_LINE if ( not temp . right . left and not temp . right . right ) : NEW_LINE INDENT result = temp . right NEW_LINE DEDENT DEDENT DEDENT return result 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 . right = 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 root . right . right . right . right = newnode ( 10 ) NEW_LINE result = getDeepestRightLeafNode ( root ) NEW_LINE if result : NEW_LINE INDENT print ( " Deepest ▁ Right ▁ Leaf ▁ Node ▁ : : " , result . data ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No ▁ result , ▁ right ▁ leaf ▁ not ▁ found " ) NEW_LINE DEDENT DEDENT