Construct Binary Search Tree from Array

Easy

Array Binary Search Tree Binary Tree Tree

Given an array of integers, create a Binary Search Tree (BST) from the elements of the array. The output should be the inorder traversal of the constructed BST as a string, with values separated by a space.

Example 1

Input

Output

8 10 12 15 16 20 25

Explanation. The values are inserted into a BST and then an inorder traversal is performed to get a sorted output.

Example 2

Input

[
  8,
  10,
  12
]

Output

8 10 12

Explanation. Already sorted input yields the same output after inorder traversal of the BST.

Example 3

Input

[
  12,
  8,
  10
]

Output

8 10 12

Explanation. After inserting all elements into the BST and performing an inorder traversal, the elements are in ascending order.

Example 4

Input

Output

1 5 10 15 20 30

Explanation. All integers are added to the BST and an inorder traversal provides the sorted output.

Follow-up: What would be the time complexity of your solution?

Constraints:

The input array will contain at least one element and all elements will be unique. The integers will be in the range of `[-10^5, 10^5]`.

Views: 12

Construct Binary Search Tree from Array

Solution

Judge

Construct Binary Search Tree from Array

Discussion (0)

Solution

Judge