Kth ancestor of a node in binary tree | Set 2 | A Binary Tree Node ; recursive function to calculate Kth ancestor ; Base case ; print the kth ancestor ; return None to stop further backtracking ; return current node to previous call ; Driver Code ; prkth ancestor of given node ; check if parent is not None , it means there is no Kth ancestor of the node
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 kthAncestorDFS ( root , node , k ) : NEW_LINE INDENT if ( not root ) : NEW_LINE INDENT return None NEW_LINE DEDENT if ( root . data == node or ( kthAncestorDFS ( root . left , node , k ) ) or ( kthAncestorDFS ( root . right , node , k ) ) ) : NEW_LINE INDENT if ( k [ 0 ] > 0 ) : NEW_LINE INDENT k [ 0 ] -= 1 NEW_LINE DEDENT elif ( k [ 0 ] == 0 ) : NEW_LINE INDENT print ( " Kth ▁ ancestor ▁ is : " , root . data ) NEW_LINE return None NEW_LINE DEDENT return root NEW_LINE DEDENT 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 . left . right = newNode ( 5 ) NEW_LINE k = [ 2 ] NEW_LINE node = 5 NEW_LINE parent = kthAncestorDFS ( root , node , k ) NEW_LINE if ( parent ) : NEW_LINE INDENT print ( " - 1" ) NEW_LINE DEDENT DEDENT