Show problems as
Classic problem #108EasyArrayDivide and ConquerTreeBinary Search TreeBinary Tree

Convert Sorted Array to Binary Search Tree

Real-world version: Balanced Marker Index
Tracked in this browser only
Read Convert Sorted Array to Binary Search Tree on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstMirror & Symmetry · Binary Trees & BST, animated step by step

A survey line carries pegs at known offsets from its datum, given as markers in strictly increasing order. An offset is signed: pegs behind the datum are negative.

Build a two-branch lookup tree over the pegs so that:

  • every peg sits at exactly one node and every node carries exactly one peg;
  • at any node, every peg in its left branch is below that node's own peg and every peg in its right branch is above it;
  • the tree is depth balanced, meaning that at every node the depths of its two branches differ by at most one.

More than one tree can meet those three rules, so build the single tree pinned down by this rule: the peg at a node is the middle peg of the stretch of markers that node covers, and when that stretch holds an even number of pegs, take the lower of its two middle pegs.

Return the tree as a listing read off one depth at a time, left to right. Slot 0 holds the top node. Each node that appears in the listing claims the next two free slots for its branches, the left branch first and the right branch second. A slot holding null carries no node and claims no slots of its own. Leave off any null slots at the end of the listing.

Examples

Example 1

Input
markers = [-6, 1, 4, 9]
Output
[1, -6, 4, null, null, null, 9]

The stretch of four pegs has 1 and 4 in the middle, so the top node takes the lower one, 1. Its left branch covers -6 alone and its right branch covers 4 and 9, where 4 is the lower of that pair's middles and 9 sits above it. Both branches of the top node are one deep and two deep, within the allowed gap.

Example 2

Input
markers = [2, 5, 7, 11, 14, 20, 23]
Output
[11, 5, 20, 2, 7, 14, 23]

Seven pegs give 11 as the middle peg, then 5 and 20 as the middles of the two halves, and the remaining four pegs fill the third depth. Every peg to the left of a node is below it and every peg to the right is above it.

Example 3

Input
markers = [8]
Output
[8]

One peg means one node with no branches, and the two empty slots after it fall at the end of the listing, so they are left off.

Constraints

  • 1 <= markers.length <= 10^4
  • -10^4 <= markers[i] <= 10^4
  • markers is given in strictly increasing order

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def balanced_marker_index(markers: list[int]) -> list[int | None]:
Java
public Integer[] balancedMarkerIndex(int[] markers)

More on the same topics