Populate Inorder Successor for all nodes | Tree node ; Set next of p and all descendants of p by traversing them in reverse Inorder ; The first visited node will be the rightmost node next of the rightmost node will be NULL ; First set the next pointer in right subtree ; Set the next as previously visited node in reverse Inorder ; Change the prev for subsequent node ; Finally , set the next pointer in left subtree ; UTILITY FUNCTIONS Helper function that allocates a new node with the given data and None left and right pointers . ; Driver Code Constructed binary tree is 10 / \ 8 12 / 3 ; Populates nextRight pointer in all nodes ; Let us see the populated values ; - 1 is printed if there is no successor
class Node : 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 self . next = None NEW_LINE DEDENT DEDENT next = None NEW_LINE def populateNext ( p ) : NEW_LINE INDENT global next NEW_LINE if ( p != None ) : NEW_LINE INDENT populateNext ( p . right ) NEW_LINE p . next = next NEW_LINE next = p NEW_LINE populateNext ( p . left ) NEW_LINE DEDENT DEDENT def newnode ( data ) : NEW_LINE INDENT node = Node ( 0 ) NEW_LINE node . data = data NEW_LINE node . left = None NEW_LINE node . right = None NEW_LINE node . next = None NEW_LINE return ( node ) NEW_LINE DEDENT root = newnode ( 10 ) NEW_LINE root . left = newnode ( 8 ) NEW_LINE root . right = newnode ( 12 ) NEW_LINE root . left . left = newnode ( 3 ) NEW_LINE p = populateNext ( root ) NEW_LINE ptr = root . left . left NEW_LINE while ( ptr != None ) : NEW_LINE INDENT out = 0 NEW_LINE if ( ptr . next != None ) : NEW_LINE INDENT out = ptr . next . data NEW_LINE DEDENT else : NEW_LINE INDENT out = - 1 NEW_LINE DEDENT print ( " Next ▁ of " , ptr . data , " is " , out ) NEW_LINE ptr = ptr . next NEW_LINE DEDENT