Lowest Common Ancestor of the deepest leaves of a Binary Tree | Node of a Binary Tree ; Function to find the depth of the Binary Tree ; If root is not null ; Left recursive subtree ; Right recursive subtree ; Returns the maximum depth ; Function to perform the depth first search on the binary tree ; If root is null ; If curr is equal to depth ; Left recursive subtree ; Right recursive subtree ; If left and right are not null ; Return left , if left is not null Otherwise return right ; Function to find the LCA of the deepest nodes of the binary tree ; If root is null ; Stores the deepest depth of the binary tree ; Return the LCA of the nodes at level depth ; Driver Code ; Given Binary Tree
class Node : NEW_LINE INDENT def __init__ ( self , d ) : NEW_LINE INDENT self . data = d NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def finddepth ( root ) : NEW_LINE INDENT if ( not root ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT left = finddepth ( root . left ) NEW_LINE right = finddepth ( root . right ) NEW_LINE return 1 + max ( left , right ) NEW_LINE DEDENT def dfs ( root , curr , depth ) : NEW_LINE INDENT if ( not root ) : NEW_LINE INDENT return None NEW_LINE DEDENT if ( curr == depth ) : NEW_LINE INDENT return root NEW_LINE DEDENT left = dfs ( root . left , curr + 1 , depth ) NEW_LINE right = dfs ( root . right , curr + 1 , depth ) NEW_LINE if ( left != None and right != None ) : NEW_LINE INDENT return root NEW_LINE DEDENT return left if left else right NEW_LINE DEDENT def lcaOfDeepestLeaves ( root ) : NEW_LINE INDENT if ( not root ) : NEW_LINE INDENT return None NEW_LINE DEDENT depth = finddepth ( root ) - 1 NEW_LINE return dfs ( root , 0 , depth ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT 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 . left . right = Node ( 5 ) NEW_LINE root . right . left = Node ( 6 ) NEW_LINE root . right . right = Node ( 7 ) NEW_LINE root . right . left . left = Node ( 8 ) NEW_LINE root . right . left . right = Node ( 9 ) NEW_LINE print ( lcaOfDeepestLeaves ( root ) . data ) NEW_LINE DEDENT