Reverse tree path | CPP program for the above approach ; Function to print inorder traversal of the tree ; Utility function to track root to leaf paths ; Check if root is null then return ; Store the node in path array ; Check if we find the node upto which oath needs to be reversed ; Current path array contains the path which needs to be reversed ; Swap the data of two nodes ; Check if the node is a leaf node then return ; Call utility function for left and right subtree recursively ; Function to reverse tree path ; Initialize a vector to store paths ; Driver Code ; 7 / \ 6 5 / \ / \ 4 3 2 1
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define nl  " NEW_LINE " class Node { public : int data ; Node * left ; Node * right ; Node ( int value ) { data = value ; } } ; void inorder ( Node * temp ) { if ( temp == NULL ) return ; inorder ( temp -> left ) ; cout << temp -> data << " ▁ " ; inorder ( temp -> right ) ; } void reverseTreePathUtil ( Node * root , vector < Node * > path , int pathLen , int key ) { if ( root == NULL ) return ; path [ pathLen ] = root ; pathLen ++ ; if ( root -> data == key ) { int i = 0 , j = pathLen - 1 ; while ( i < j ) { int temp = path [ i ] -> data ; path [ i ] -> data = path [ j ] -> data ; path [ j ] -> data = temp ; i ++ ; j -- ; } } if ( ! root -> left and ! root -> right ) return ; reverseTreePathUtil ( root -> left , path , pathLen , key ) ; reverseTreePathUtil ( root -> right , path , pathLen , key ) ; } void reverseTreePath ( Node * root , int key ) { if ( root == NULL ) return ; vector < Node * > path ( 50 , NULL ) ; reverseTreePathUtil ( root , path , 0 , key ) ; } int main ( ) { Node * root = new Node ( 7 ) ; root -> left = new Node ( 6 ) ; root -> right = new Node ( 5 ) ; root -> left -> left = new Node ( 4 ) ; root -> left -> right = new Node ( 3 ) ; root -> right -> left = new Node ( 2 ) ; root -> right -> right = new Node ( 1 ) ; int key = 4 ; reverseTreePath ( root , key ) ; inorder ( root ) ; return 0 ; }