Print Postorder traversal from given Inorder and Preorder traversals | C ++ program to print postorder traversal from preorder and inorder traversals ; A utility function to search x in arr [ ] of size n ; Prints postorder traversal from given inorder and preorder traversals ; The first element in pre [ ] is always root , search it in in [ ] to find left and right subtrees ; If left subtree is not empty , print left subtree ; If right subtree is not empty , print right subtree ; Print root ; Driver program to test above functions
#include <iostream> NEW_LINE using namespace std ; int search ( int arr [ ] , int x , int n ) { for ( int i = 0 ; i < n ; i ++ ) if ( arr [ i ] == x ) return i ; return -1 ; } void printPostOrder ( int in [ ] , int pre [ ] , int n ) { int root = search ( in , pre [ 0 ] , n ) ; if ( root != 0 ) printPostOrder ( in , pre + 1 , root ) ; if ( root != n - 1 ) printPostOrder ( in + root + 1 , pre + root + 1 , n - root - 1 ) ; cout << pre [ 0 ] << " ▁ " ; } int main ( ) { int in [ ] = { 4 , 2 , 5 , 1 , 3 , 6 } ; int pre [ ] = { 1 , 2 , 4 , 5 , 3 , 6 } ; int n = sizeof ( in ) / sizeof ( in [ 0 ] ) ; cout << " Postorder ▁ traversal ▁ " << endl ; printPostOrder ( in , pre , n ) ; return 0 ; }