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 ; function that allocates a new node with the given data and NULL left and right pointers . ; Function to modify tree ; if the left tree exists ; get the right - most of the original left subtree ; set root right to left subtree ; if the right subtree does not exists we are done ! ; set right pointer of right - most of the original left subtree ; modify the rightsubtree ; printing using right pointer only ; Driver program to test above functions ; Constructed binary tree is 10 / \ 8 2 / \ 3 5
#include <bits/stdc++.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 ) ; } struct Node * modifytree ( struct Node * root ) { struct Node * right = root -> right ; struct Node * rightMost = root ; if ( root -> left ) { rightMost = modifytree ( root -> left ) ; root -> right = root -> left ; root -> left = NULL ; } if ( ! right ) return rightMost ; rightMost -> right = right ; rightMost = modifytree ( right ) ; return rightMost ; } 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 ; }