Check if there is a root to leaf path with given sequence | Class of Node ; Util function ; If root is NULL or reached end of the array ; If current node is leaf ; If current node is equal to arr [ index ] this means that till this level path has been matched and remaining path can be either in left subtree or right subtree . ; Function to check given sequence of root to leaf path exist in tree or not . index represents current element in sequence of rooth to leaf path ; Driver Code ; arr [ ] : sequence of root to leaf path
class Node : NEW_LINE INDENT def __init__ ( self , val ) : NEW_LINE INDENT self . val = val NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def existPathUtil ( root , arr , n , index ) : NEW_LINE INDENT if not root or index == n : NEW_LINE INDENT return False NEW_LINE DEDENT if not root . left and not root . right : NEW_LINE INDENT if root . val == arr [ index ] and index == n - 1 : NEW_LINE INDENT return True NEW_LINE DEDENT return False NEW_LINE DEDENT return ( ( index < n ) and ( root . val == arr [ index ] ) and ( existPathUtil ( root . left , arr , n , index + 1 ) or existPathUtil ( root . right , arr , n , index + 1 ) ) ) NEW_LINE DEDENT def existPath ( root , arr , n , index ) : NEW_LINE INDENT if not root : NEW_LINE INDENT return ( n == 0 ) NEW_LINE DEDENT return existPathUtil ( root , arr , n , 0 ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 5 , 8 , 6 , 7 ] NEW_LINE n = len ( arr ) NEW_LINE root = Node ( 5 ) NEW_LINE root . left = Node ( 3 ) NEW_LINE root . right = Node ( 8 ) NEW_LINE root . left . left = Node ( 2 ) NEW_LINE root . left . right = Node ( 4 ) NEW_LINE root . left . left . left = Node ( 1 ) NEW_LINE root . right . left = Node ( 6 ) NEW_LINE root . right . left . right = Node ( 7 ) NEW_LINE if existPath ( root , arr , n , 0 ) : NEW_LINE INDENT print ( " Path ▁ Exists " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " Path ▁ does ▁ not ▁ Exist " ) NEW_LINE DEDENT DEDENT