Find next right node of a given key | Set 2 | class to create a new tree node ; Function to find next node for given node in same level in a binary tree by using pre - order traversal ; return None if tree is empty ; if desired node is found , set value_level to current level ; if value_level is already set , then current node is the next right node ; recurse for left subtree by increasing level by 1 ; if node is found in left subtree , return it ; recurse for right subtree by increasing level by 1 ; Function to find next node of given node in the same level in given binary tree ; A utility function to test above functions ; Driver Code ; Let us create binary tree given in the above example
class newNode : NEW_LINE INDENT def __init__ ( self , key ) : NEW_LINE INDENT self . key = key NEW_LINE self . left = self . right = None NEW_LINE DEDENT DEDENT def nextRightNode ( root , k , level , value_level ) : NEW_LINE INDENT if ( root == None ) : NEW_LINE INDENT return None NEW_LINE DEDENT if ( root . key == k ) : NEW_LINE INDENT value_level [ 0 ] = level NEW_LINE return None NEW_LINE DEDENT elif ( value_level [ 0 ] ) : NEW_LINE INDENT if ( level == value_level [ 0 ] ) : NEW_LINE INDENT return root NEW_LINE DEDENT DEDENT leftNode = nextRightNode ( root . left , k , level + 1 , value_level ) NEW_LINE if ( leftNode ) : NEW_LINE INDENT return leftNode NEW_LINE DEDENT return nextRightNode ( root . right , k , level + 1 , value_level ) NEW_LINE DEDENT def nextRightNodeUtil ( root , k ) : NEW_LINE INDENT value_level = [ 0 ] NEW_LINE return nextRightNode ( root , k , 1 , value_level ) NEW_LINE DEDENT def test ( root , k ) : NEW_LINE INDENT nr = nextRightNodeUtil ( root , k ) NEW_LINE if ( nr != None ) : NEW_LINE INDENT print ( " Next ▁ Right ▁ of " , k , " is " , nr . key ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No ▁ next ▁ right ▁ node ▁ found ▁ for " , k ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = newNode ( 10 ) NEW_LINE root . left = newNode ( 2 ) NEW_LINE root . right = newNode ( 6 ) NEW_LINE root . right . right = newNode ( 5 ) NEW_LINE root . left . left = newNode ( 8 ) NEW_LINE root . left . right = newNode ( 4 ) NEW_LINE test ( root , 10 ) NEW_LINE test ( root , 2 ) NEW_LINE test ( root , 6 ) NEW_LINE test ( root , 5 ) NEW_LINE test ( root , 8 ) NEW_LINE test ( root , 4 ) NEW_LINE DEDENT