Modify a binary tree to get preorder traversal using right pointers only | A binary tree node has data , left child and right child ; An iterative process to set the right pointer of Binary tree ; Base Case ; Create an empty stack and append root to it ; Pop all items one by one . Do following for every popped item a ) prit b ) append its right child c ) append its left child Note that right child is appended first so that left is processed first ; Pop the top item from stack ; append right and left children of the popped node to stack ; check if some previous node exists ; set the right pointer of previous node to currrent ; set previous node as current node ; printing using right pointer only ; Constructed binary tree is 10 / \ 8 2 / \ 3 5
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 modifytree ( root ) : NEW_LINE INDENT if ( root == None ) : NEW_LINE INDENT return NEW_LINE DEDENT nodeStack = [ ] NEW_LINE nodeStack . append ( root ) NEW_LINE pre = None NEW_LINE while ( len ( nodeStack ) ) : NEW_LINE INDENT node = nodeStack [ - 1 ] NEW_LINE nodeStack . pop ( ) NEW_LINE if ( node . right ) : NEW_LINE INDENT nodeStack . append ( node . right ) NEW_LINE DEDENT if ( node . left ) : NEW_LINE INDENT nodeStack . append ( node . left ) NEW_LINE DEDENT if ( pre != None ) : NEW_LINE INDENT pre . right = node NEW_LINE DEDENT pre = node NEW_LINE DEDENT DEDENT def printpre ( root ) : NEW_LINE INDENT while ( root != None ) : NEW_LINE INDENT print ( root . data , end = " ▁ " ) NEW_LINE root = root . right NEW_LINE DEDENT DEDENT root = newNode ( 10 ) NEW_LINE root . left = newNode ( 8 ) NEW_LINE root . right = newNode ( 2 ) NEW_LINE root . left . left = newNode ( 3 ) NEW_LINE root . left . right = newNode ( 5 ) NEW_LINE modifytree ( root ) NEW_LINE printpre ( root ) NEW_LINE