Reverse tree path | CPP program to Reverse Tree path ; A Binary Tree Node ; ' data ' is input . We need to reverse path from root to data . ' level ' is current level . ' temp ' that stores path nodes . ' nextpos ' used to pick next item for reversing . ; return NULL if root NULL ; Final condition if the node is found then ; store the value in it 's level ; change the root value with the current next element of the map ; increment in k for the next element ; store the data in perticular level ; We go to right only when left does not contain given data . This way we make sure that correct path node is stored in temp [ ] ; If current node is part of the path , then do reversing . ; return NULL if not element found ; Reverse Tree path ; store per level data ; it is for replacing the data ; reverse tree path ; INORDER ; Utility function to create a new tree node ; Driver program to test above functions ; Let us create binary tree shown in above diagram ; 7 / \ 6 5 / \ / \ 4 3 2 1 ; Reverse Tree Path ; Traverse inorder
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; struct Node * left , * right ; } ; Node * reverseTreePathUtil ( Node * root , int data , map < int , int > & temp , int level , int & nextpos ) { if ( root == NULL ) return NULL ; if ( data == root -> data ) { temp [ level ] = root -> data ; root -> data = temp [ nextpos ] ; nextpos ++ ; return root ; } temp [ level ] = root -> data ; Node * left , * right ; left = reverseTreePathUtil ( root -> left , data , temp , level + 1 , nextpos ) ; if ( left == NULL ) right = reverseTreePathUtil ( root -> right , data , temp , level + 1 , nextpos ) ; if ( left right ) { root -> data = temp [ nextpos ] ; nextpos ++ ; return ( left ? left : right ) ; } return NULL ; } void reverseTreePath ( Node * root , int data ) { map < int , int > temp ; int nextpos = 0 ; reverseTreePathUtil ( root , data , temp , 0 , nextpos ) ; } void inorder ( Node * root ) { if ( root != NULL ) { inorder ( root -> left ) ; cout << root -> data << " ▁ " ; inorder ( root -> right ) ; } } Node * newNode ( int data ) { Node * temp = new Node ; temp -> data = data ; temp -> left = temp -> right = NULL ; return temp ; } int main ( ) { Node * root = newNode ( 7 ) ; root -> left = newNode ( 6 ) ; root -> right = newNode ( 5 ) ; root -> left -> left = newNode ( 4 ) ; root -> left -> right = newNode ( 3 ) ; root -> right -> left = newNode ( 2 ) ; root -> right -> right = newNode ( 1 ) ; int data = 4 ; reverseTreePath ( root , data ) ; inorder ( root ) ; return 0 ; }