Construct Binary Search Tree from Preorder Traversal

Challenge Points: 20

Level: Medium

You are given an integer array preorder, which represents the preorder traversal of a Binary Search Tree (BST). Your task is to reconstruct the BST and return its root.

It is guaranteed that the provided input can always form a valid BST.

In a Binary Search Tree, for every node:

All values in the left subtree are strictly less than the node’s value.
All values in the right subtree are strictly greater than the node’s value.

In preorder traversal, we visit the current node first, then recursively traverse the left subtree, followed by the right subtree.

Example 1:

Input: preorder = [6, 3, 2, 5, 9, 8, 11]

Output: [6, 3, 9, 2, 5, 8, 11]

Example 2:

Input: preorder = [4, 2, 7]

Output: [4, 2, 7]

to Continue

Accepted:

Submission:

Report an issue

Code

You need toto run or submitYou need toto run or submit

Test Case

Test Result