BST reconstruction

Node *reconstruct(const vector<int> &arr) {
  stack<Node*> S;
  Node *root = 0;

  for (const int &value : arr) {
    Node *current = new Node;
    current->data = value;
    current->left = current->right = 0;

    if (S.empty()) {
      S.push(current);
      root = current;
      continue;
    }

    Node *top = S.top();
    // Left subtree will contain values <= current node. Right subtree will contain values which
    // are strictly greater than current node.
    if (current->data <= top->data) {
      top->left = current;
      S.push(current);
      continue;
    }

    // We have encountered a right descendant of some node which is on our stack. Keep popping
    // nodes until we find a node with value greater than or equal to current node. The last node
    // popped is the desired root.
    Node *last_popped = 0;
    while (!S.empty() && (S.top())->data < current->data) {
      last_popped = S.top();
      S.pop();
    }

    last_popped->right = current;
    S.push(current);
  }
  return root;
}