build bst from pre order array

buildBstFromPreOrder.cpp

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

struct ListNode {
    int val;
    ListNode *left;
    ListNode *right;
    ListNode(int _val) : val(_val), left(NULL), right(NULL) {}  
};

// the stack contains the nodes along the path, whose right child is not populated
ListNode * buildBST(vector<int> preorder) {
    stack<ListNode*> path;
    ListNode *root = NULL;
    for (int i = 0; i < preorder.size(); i++) {
        if (path.empty()) {
            root = new ListNode(preorder[i]);
			path.push(root);
        } else if (path.top()->val >= preorder[i]) {
            path.top()->left = new ListNode(preorder[i]);
            path.push(path.top()->left);
        } else {
            ListNode* parent = path.top();
            path.pop();
            while (!path.empty() && path.top()->val < preorder[i]) {
                parent = path.top();
                path.pop();
            }
            parent->right = new ListNode(preorder[i]);
            path.push(parent->right);
        }
    }
    return root;
}

void printTreePre(ListNode *root) {
    if (root == NULL)
        return;
    cout << root->val << endl;
    printTreePre(root->left);
    printTreePre(root->right);
}

void printTreeIn(ListNode *root) {
    if (root == NULL)
        return;
    printTreeIn(root->left);
    cout << root->val << endl;
    printTreeIn(root->right);
}

int main() {
    int arr[8] = {6, 3, 1, 4, 5, 7, 9, 8};
    vector<int> vec(arr, arr + 8);
    ListNode *root = buildBST(vec);
    cout << "=== PreOrder ===" << endl;
    printTreePre(root);
    cout << "=== InOrder ===" << endl;
    printTreeIn(root);

    return 0;
}