Preorder traversal of a BST

Moderate

0/80

Average time to solve is 15m

Contributed by

55 upvotes

Asked in companies

Problem statement

You have been given an array/list 'PREORDER' representing the preorder traversal of a BST with 'N' nodes. All the elements in the given array have distinct values.

Your task is to construct a binary search tree that matches the given preorder traversal.

A binary search tree (BST) is a binary tree data structure that has the following properties:

• The left subtree of a node contains only nodes with data less than the node’s data.
• The right subtree of a node contains only nodes with data greater than the node’s data.
• Both the left and right subtrees must also be binary search trees.

Note:

It is guaranteed that a BST can be always constructed from the given preorder traversal. Hence, the answer will always exist.

Example:

From PREORDER = [20, 10, 5, 15, 13, 35, 30, 42] , the following BST can be constructed:

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of each test case contains a single integer 'N' denoting the number of nodes in BST.

The second line of each test case contains 'N' single space-separated integers representing the preorder traversal of BST.

Output Format:

Print the inorder traversal of the constructed BST where all nodes are printed in a single-space separated manner.

Output for every test case will be printed in a separate line.

Note:
You don't need to print anything. It has already been taken care of. Just implement the function.

Constraints :

1 <= T <= 100
1 <= N <= 5000
0 <= data <= 10^5

Where 'data' denotes data contained in the nodes of the binary search tree.

Time Limit: 1 sec

Sample Input 1:

1
6
10 4 3 7 40 55

Sample Output 1:

3 5 7 10 40 50

Explanation For Sample Output1:

From the given preorder traversal, the following BST can be constructed:

The inorder traversal of the given BST is [1, 4, 7, 10, 40, 55].

Sample Input 2:

2
7
15 10 7 13 21 20 25 
3
1 2 4

Sample Output 2:

7 10 13 15 20 21 25
1 2 4

Console