Modify a binary tree to get preorder traversal using right pointers only | C ++ code to modify binary tree for traversal using only right pointer ; A binary tree node has data , left child and right child ; Helper function that allocates a new node with the given data and NULL left and right pointers . ; An iterative process to set the right pointer of Binary tree ; Base Case ; Create an empty stack and push root to it ; Pop all items one by one . Do following for every popped item a ) print it b ) push its right child c ) push its left child Note that right child is pushed first so that left is processed first ; Pop the top item from stack ; Push 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 ; Driver code ; Constructed binary tree is 10 / \ 8 2 / \ 3 5
#include <iostream> NEW_LINE #include <stack> NEW_LINE #include <stdio.h> NEW_LINE #include <stdlib.h> NEW_LINE using namespace std ; struct Node { int data ; struct Node * left ; struct Node * right ; } ; struct Node * newNode ( int data ) { struct Node * node = new struct Node ; node -> data = data ; node -> left = NULL ; node -> right = NULL ; return ( node ) ; } void modifytree ( struct Node * root ) { if ( root == NULL ) return ; stack < Node * > nodeStack ; nodeStack . push ( root ) ; struct Node * pre = NULL ; while ( nodeStack . empty ( ) == false ) { struct Node * node = nodeStack . top ( ) ; nodeStack . pop ( ) ; if ( node -> right ) nodeStack . push ( node -> right ) ; if ( node -> left ) nodeStack . push ( node -> left ) ; if ( pre != NULL ) { pre -> right = node ; } pre = node ; } } void printpre ( struct Node * root ) { while ( root != NULL ) { cout << root -> data << " ▁ " ; root = root -> right ; } } int main ( ) { struct Node * root = newNode ( 10 ) ; root -> left = newNode ( 8 ) ; root -> right = newNode ( 2 ) ; root -> left -> left = newNode ( 3 ) ; root -> left -> right = newNode ( 5 ) ; modifytree ( root ) ; printpre ( root ) ; return 0 ; }