Contruct BST from Preorder Traversal O(n^2)

constructBSTFromPreorder.cpp

int findIndex(vector<int>& pre, int l, int r, int v) {
  while (l <= r) {
    if (pre[l] > v) return l;
    l++;
  }

  return -1;
}

TreeNode* buildTree(vector<int>& pre, int s, int e) {
  if (s > e) return nullptr;

  TreeNode* root = new TreeNode(pre[s]);
  int rightIndex = findIndex(pre, s + 1, e, root->val);
  if (rightIndex != -1) {
    root->left = buildTree(pre, s + 1, rightIndex - 1);
    root->right = buildTree(pre, rightIndex, e);
  }
  else {
    root->left = buildTree(pre, s + 1, e);
  }
  return root;
}

int main() {
  vector<int> pre = { 10, 5, 1, 7, 40, 50 };
  TreeNode* root = buildTree(pre, 0, pre.size() - 1);
  levelOrderTraversal(root);
}