Find postorder traversal of BST from preorder traversal | C ++ program for finding postorder traversal of BST from preorder traversal ; Function to find postorder traversal from preorder traversal . ; If entire preorder array is traversed then return as no more element is left to be added to post order array . ; If array element does not lie in range specified , then it is not part of current subtree . ; Store current value , to be printed later , after printing left and right subtrees . Increment preIndex to find left and right subtrees , and pass this updated value to recursive calls . ; All elements with value between minval and val lie in left subtree . ; All elements with value between val and maxval lie in right subtree . ; Function to find postorder traversal . ; To store index of element to be traversed next in preorder array . This is passed by reference to utility function . ; Driver code ; Calling function
#include <bits/stdc++.h> NEW_LINE using namespace std ; void findPostOrderUtil ( int pre [ ] , int n , int minval , int maxval , int & preIndex ) { if ( preIndex == n ) return ; if ( pre [ preIndex ] < minval pre [ preIndex ] > maxval ) { return ; } int val = pre [ preIndex ] ; preIndex ++ ; findPostOrderUtil ( pre , n , minval , val , preIndex ) ; findPostOrderUtil ( pre , n , val , maxval , preIndex ) ; cout << val << " ▁ " ; } void findPostOrder ( int pre [ ] , int n ) { int preIndex = 0 ; findPostOrderUtil ( pre , n , INT_MIN , INT_MAX , preIndex ) ; } int main ( ) { int pre [ ] = { 40 , 30 , 35 , 80 , 100 } ; int n = sizeof ( pre ) / sizeof ( pre [ 0 ] ) ; findPostOrder ( pre , n ) ; return 0 ; }