Skills101
← All coding problems

Convert Sorted Array to BST

easyTrees & BST II+10 XPTime limit 2s

Turn a sorted array of distinct numbers into a height-balanced binary search tree: for every node, the sizes of its left and right subtrees differ by at most one.

To make the answer unique, always pick the middle element as the root: for a range of indices lo..hi, the root is index (lo + hi) / 2 rounded down (so for an even-length range, the left one of the two middles). Then build the left subtree from the elements before it and the right subtree from the elements after it, by the same rule.

Input:

  • line 1: n
  • line 2: n distinct numbers in increasing order

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⁴, −10⁴ ≤ value ≤ 10⁴.

Think about it: a recursive build(lo, hi) that creates the middle node and recurses on both halves — O(n) nodes, height about log₂ n. Then print the tree level by level with a queue.

Sample input 1

5
-10 -3 0 5 9

Sample output 1

0 -10 5 null -3 null 9

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.