#include<iostream>
#include<stack>
using namespace std;

class node{
  public:
  int value;
  node* left;
  node* right;
  node(int value)
  {
    this->value = value;
    left = NULL;
    right = NULL;
  }
};

node* preorderToTree(int* a, int length)
{
  if(length==0)
    return NULL;
  node* root = new node(a[0]);
  stack<node*> s;
  s.push(root);
  for(int i=1; i<length; i++)
  {
    node* tmp = new node(a[i]);
    if(tmp->value < s.top()->value)
    {
      s.top()->left = tmp;
    }
    else
    {
      node* popped = NULL;
      while(!s.empty() && tmp->value > s.top()->value)
      {
        popped = s.top();
        s.pop();
      }
      popped->right = tmp;
    }
    s.push(tmp);
  }
  return root;
}

void inorder(node* root)
{
  if(root)
  {
    inorder(root->left);
    cout<<root->value<<" ";
    inorder(root->right);
  }
}

int main()
{
  int a[] = {10, 8, 5, 2, 6, 7, 9, 20, 15, 25, 23};
  node* root = NULL;
  root = preorderToTree(a, sizeof(a)/sizeof(a[0]));
  inorder(root);
}