Skills101
← All coding problems

Construct BST from Preorder

mediumTrees & BST II+20 XPTime limit 2s

You are given the preorder traversal (node, then left subtree, then right subtree) of a binary search tree with distinct values. Rebuild the tree and print it.

For a BST, the preorder alone is enough: the first value is the root, the smaller values that follow form the left subtree, and the rest form the right subtree.

Input:

  • line 1: n — the number of nodes
  • line 2: the preorder sequence (it always comes from a real BST)

Output: the tree in level order (top to bottom, left to right) with null for a missing child and trailing nulls left out — e.g. 3 9 20 null null 15 7; an empty tree is null.

Constraints: 1 ≤ n ≤ 10⁴, distinct values between −10⁵ and 10⁵. The tree's height is at most 500.

Think about it: inserting the values one by one into an empty BST gives the right tree, but costs O(n·h). The O(n) way: read the sequence once with a recursive build(upperBound) — the next value becomes a node only if it is below the bound; its left subtree gets the node's value as the new bound, its right subtree keeps the old bound.

Sample input 1

6
8 5 1 7 10 12

Sample output 1

8 5 10 1 7 null 12

Sample input 2

2
1 3

Sample output 2

1 null 3

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…

Log in to run and submit your code — it's free.