Preorder to Postorder

Recursive solution to a problem of geeksforgeeks.
http://practice.geeksforgeeks.org/problems/preorder-to-postorder/0

Problem:
Given an array representing preorder traversal of BST, print its postorder traversal.



Input:
The first line of input contains an integer T denoting the number of test cases.
The first line of each test case is N,N is the size of array.
The second line of each test case contains N input A[i].

Output:
Postorder traversal of the given preorder traversal is printed. Otherwise 'NO' is printed.

Constraints:
1 <=T<= 55
1 <= N <= 1000
1 <= arr[i] <= 1000

Example:

Input:
3
5
40 30 35 80 100
8
40 30 32 35 80 90 100 120
8
7  9 6 1 4 2 3 40

Output:
35 30 100 80 40
35 32 30 120 100 90 80 40
NO

Code:

#include<bits/stdc++.h>
using namespace std;
 
int n; //number of elements in a test case
int arr[10000]; // array to store preorder traversal
int ans[10000]; // array to store postorder traversal in reverse order
int k=0; // index in ans[] array
bool ans_no = 0; // this boolean variable will be set if answer does not exist for a test case
 
// returns,
// index of an element in array-range [s...e] which is greater than "ele"
// if not exist then -1
// also checks for preorder correctness
int indexof(int s, int e, int ele)
{
int ret=-1;
 
// finding index
for(int i=s; i<=e;i++){
if(arr[i]>ele){
ret=i;
break;
}
}
 
if(ret==-1) return ret;
 
// checking all element in range [s+1...ret-1] are lesser
// if not then set "ans_no"
for(int i=s+1; i<=ret-1; i++){
if(arr[i]>ele){
ans_no=1;
return ret;
}
}
 
// checking all element in range [ret...e] are greater
// if not then set "ans_no"
for(int i=ret; i<=e; i++){
if(arr[i]<ele){
ans_no=1;
return ret;
}
}
 
return ret;
}
 
void postorder(int l, int r)
{
// if indices are beyond boundary
if(l<0 || r>=n || l>r) return;
 
// storing leftmost element (i.e. at index = l ) in ans[] array
ans[k++] = arr[l];
 
// if l==r then no need to recurse
if(l==r){
return;
}
 
// finding index of an element in array-range [l+1...r] which is greater than arr[l]
int ind = indexof(l+1, r, arr[l]);
 
// if ans dose not exist then return
if(ans_no) return;
 
// if "ind" is set then
// recurse of right part first i.e. postorder(ind, r);
// then for left part i.e. postorder(l+1, ind-1);
// else if ind==-1
// then recurse for remaining whole part i.e. postorder(l+1, r);
// this would occur if a node in BST does not have left or right child.
if(ind!=-1){
postorder(ind, r);
postorder(l+1, ind-1);
}
else{
postorder(l+1, r);
}
}
 
void solve()
{
// resetting global variables
ans_no=0;
k=0;
 
// scanning input
cin>>n;
for(int i=0;i<n;i++){
cin>>arr[i];
}
 
// call to postorder
postorder(0, n-1);
 
// if ans doesn't exist, print NO, and return
if(ans_no){
cout<<"NO"<<endl;
return;
}
 
// print ans
for(int i=k-1;i>=0;i--){
cout<<ans[i]<<" ";
}
 
cout<<endl;
}
 
int main()
{
ios_base::sync_with_stdio(0);
 
int t=1; cin>>t;
while(t--){
solve();
}
 
return 0;
}

Ideone Link: https://ideone.com/3Dz6Yz