Number of turns to reach from one node to other in binary tree | A Binary Tree Node ; Utility function to create a new tree Node ; Utility function to find the LCA of two given values n1 and n2 . ; Base case ; If either n1 or n2 matches with root 's key, report the presence by  returning root (Note that if a key  is ancestor of other, then the  ancestor key becomes LCA ; Look for keys in left and right subtrees ; If both of the above calls return Non - NULL , then one key is present in once subtree and other is present in other , So this node is the LCA ; Otherwise check if left subtree or right subtree is LCA ; function count number of turn need to reach given node from it 's LCA we have two way to ; if found the key value in tree ; Case 1 : ; Case 2 : ; Function to find nodes common to given two nodes ; there is no path between these two node ; case 1 : ; count number of turns needs to reached the second node from LCA ; count number of turns needs to reached the first node from LCA ; case 2 : ; count number of turns needs to reached the second node from LCA ; count number of turns needs to reached the first node from LCA1 ; Driver Code ; Let us create binary tree given in the above example
class Node : NEW_LINE INDENT def __init__ ( self ) : NEW_LINE INDENT self . key = 0 NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def newNode ( key : int ) -> Node : NEW_LINE INDENT temp = Node ( ) NEW_LINE temp . key = key NEW_LINE temp . left = None NEW_LINE temp . right = None NEW_LINE return temp NEW_LINE DEDENT def findLCA ( root : Node , n1 : int , n2 : int ) -> Node : NEW_LINE INDENT if root is None : NEW_LINE INDENT return None NEW_LINE DEDENT if root . key == n1 or root . key == n2 : NEW_LINE INDENT return root NEW_LINE DEDENT left_lca = findLCA ( root . left , n1 , n2 ) NEW_LINE right_lca = findLCA ( root . right , n1 , n2 ) NEW_LINE if left_lca and right_lca : NEW_LINE INDENT return root NEW_LINE DEDENT return ( left_lca if left_lca is not None else right_lca ) NEW_LINE DEDENT def countTurn ( root : Node , key : int , turn : bool ) -> bool : NEW_LINE INDENT global count NEW_LINE if root is None : NEW_LINE INDENT return False NEW_LINE DEDENT if root . key == key : NEW_LINE INDENT return True NEW_LINE DEDENT if turn is True : NEW_LINE INDENT if countTurn ( root . left , key , turn ) : NEW_LINE INDENT return True NEW_LINE DEDENT if countTurn ( root . right , key , not turn ) : NEW_LINE INDENT count += 1 NEW_LINE return True NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT if countTurn ( root . right , key , turn ) : NEW_LINE INDENT return True NEW_LINE DEDENT if countTurn ( root . left , key , not turn ) : NEW_LINE INDENT count += 1 NEW_LINE return True NEW_LINE DEDENT DEDENT return False NEW_LINE DEDENT def numberOfTurn ( root : Node , first : int , second : int ) -> int : NEW_LINE INDENT global count NEW_LINE LCA = findLCA ( root , first , second ) NEW_LINE if LCA is None : NEW_LINE INDENT return - 1 NEW_LINE DEDENT count = 0 NEW_LINE if LCA . key != first and LCA . key != second : NEW_LINE INDENT if countTurn ( LCA . right , second , False ) or countTurn ( LCA . left , second , True ) : NEW_LINE INDENT pass NEW_LINE DEDENT if countTurn ( LCA . left , first , True ) or countTurn ( LCA . right , first , False ) : NEW_LINE INDENT pass NEW_LINE DEDENT return count + 1 NEW_LINE DEDENT if LCA . key == first : NEW_LINE INDENT countTurn ( LCA . right , second , False ) NEW_LINE countTurn ( LCA . left , second , True ) NEW_LINE return count NEW_LINE DEDENT else : NEW_LINE INDENT countTurn ( LCA . right , first , False ) NEW_LINE countTurn ( LCA . left , first , True ) NEW_LINE return count NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT count = 0 NEW_LINE root = Node ( ) NEW_LINE 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 root . right . left = newNode ( 6 ) NEW_LINE root . right . right = newNode ( 7 ) NEW_LINE root . left . left . left = newNode ( 8 ) NEW_LINE root . right . left . left = newNode ( 9 ) NEW_LINE root . right . left . right = newNode ( 10 ) NEW_LINE turn = numberOfTurn ( root , 5 , 10 ) NEW_LINE if turn : NEW_LINE INDENT print ( turn ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " Not ▁ possible " ) NEW_LINE DEDENT DEDENT