Guest User

BST reconstruction

a guest
Jan 13th, 2015
201
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. Node *reconstruct(const vector<int> &arr) {
  2.   stack<Node*> S;
  3.   Node *root = 0;
  4.  
  5.   for (const int &value : arr) {
  6.     Node *current = new Node;
  7.     current->data = value;
  8.     current->left = current->right = 0;
  9.  
  10.     if (S.empty()) {
  11.       S.push(current);
  12.       root = current;
  13.       continue;
  14.     }
  15.  
  16.     Node *top = S.top();
  17.     // Left subtree will contain values <= current node. Right subtree will contain values which
  18.     // are strictly greater than current node.
  19.     if (current->data <= top->data) {
  20.       top->left = current;
  21.       S.push(current);
  22.       continue;
  23.     }
  24.  
  25.     // We have encountered a right descendant of some node which is on our stack. Keep popping
  26.     // nodes until we find a node with value greater than or equal to current node. The last node
  27.     // popped is the desired root.
  28.     Node *last_popped = 0;
  29.     while (!S.empty() && (S.top())->data < current->data) {
  30.       last_popped = S.top();
  31.       S.pop();
  32.     }
  33.  
  34.     last_popped->right = current;
  35.     S.push(current);
  36.   }
  37.   return root;
  38. }
RAW Paste Data