Skip to main content

Construct Binary Search Tree from Preorder Traversal

Problem​

Given an array of integers preorder, which represents the preorder traversal of a BST (i.e., binary search tree), construct the tree and return its root.

It is guaranteed that there is always possible to find a binary search tree with the given requirements for the given test cases.

A binary search tree is a binary tree where for every node, any descendant of Node.left has a value strictly less than Node.val, and any descendant of Node.right has a value strictly greater than Node.val.

A preorder traversal of a binary tree displays the value of the node first, then traverses Node.left, then traverses Node.right.

Solution Approach​

Expected Time complexity: O(n)O(n)

Click - to see solution code
class Solution {
   public:
    TreeNode* createBST(vector<int> nums, int i, int j) {
        if (i > j) return NULL;
        TreeNode* root = new TreeNode(nums[i]);
        if (i == j) return root;
        int k = i + 1;
        while (k <= j && nums[k] < nums[i]) k++;
        root->left = createBST(nums, i + 1, k - 1);
        root->right = createBST(nums, k, j);
        return root;
    }

    TreeNode* bstFromPreorder(vector<int>& nums) {
        return createBST(nums, 0, nums.size() - 1);
    }
};