Given a distinct sequence of keys representing the preorder sequence of a binary search tree (BST), construct a BST from it.

For example, the following BST corresponds to the preorder traversal { 15, 10, 8, 12, 20, 16, 25 }.

BST

Practice this problem

We can easily build a BST for a given preorder sequence by recursively repeating the following steps for all keys in it:

  1. Construct the root node of BST, which would be the first key in the preorder sequence.
  2. Find index i of the first key in the preorder sequence, which is greater than the root node.
  3. Recur for the left subtree with keys in the preorder sequence that appears before the i'th index (excluding the first index).
  4. Recur for the right subtree with keys in the preorder sequence that appears after the i'th index (including the i'th index).

Let’s consider the preorder traversal {15, 10, 8, 12, 20, 16, 25} to make the context more clear.

  1. The first item in the preorder sequence 15 becomes the root node.
  2. Since 20 is the first key in the preorder sequence, which greater than the root node, the left subtree consists of keys {10, 8, 12} and the right subtree consists of keys {20, 16, 25}.
  3. To construct the complete BST, recursively repeat the above steps for preorder sequence {10, 8, 12} and {20, 16, 25}.

The algorithm can be implemented as follows in C, Java, and Python:

C


Download  Run Code

Output:

Inorder traversal of BST is 8 10 12 15 16 20 25

Java


Download  Run Code

Output:

Inorder traversal of BST is 8 10 12 15 16 20 25

Python


Download  Run Code

Output:

Inorder traversal of BST is 8 10 12 15 16 20 25

The time complexity of the above solution is O(n2), where n is the size of the BST, and requires space proportional to the tree’s height for the call stack. We can reduce the time complexity to O(n) by following a different approach that doesn’t involve searching for an index that separates the left and right subtree keys in a preorder sequence:

 
We know that each node has a key that is greater than all keys present in its left subtree, but less than the keys present in the right subtree of a BST. The idea to pass the information regarding the valid range of keys for the current root node and its children in the recursion itself.

We start by setting the range as [-INFINITY, INFINITY] for the root node. It means that the root node and any of its children can have keys ranging between -INFINITY and INFINITY. Like the previous approach, construct BST’s root node from the first item in the preorder sequence. Suppose the root node has value x, recur for the right subtree with range (x, INFINITY) and recur for the left subtree with range [-INFINITY, x). To construct the complete BST, recursively set the range for each recursive call and return if the next element in preorder traversal is out of the valid range.

Following is the C++, Java, and Python program that demonstrates it:

C++


Download  Run Code

Output:

Inorder traversal of BST is 8 10 12 15 16 20 25

Java


Download  Run Code

Output:

Inorder traversal of BST is 8 10 12 15 16 20 25

Python


Download  Run Code

Output:

Inorder traversal of BST is 8 10 12 15 16 20 25