Show problems as
Classic problem #1382MediumDivide and ConquerGreedyTreeDepth-First SearchBinary Search TreeBinary Tree

Balance a Binary Search Tree

Real-world version: Rebalancing the Bin Index
Tracked in this browser only
Read Balance a Binary Search Tree on LeetCode(opens in a new tab)

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

A warehouse looks bins up through a search index. Each index card carries a bin number and hangs at most two cards below it, a left one and a right one. Every card below-and-left of a card carries a smaller bin number, and every card below-and-right carries a larger one, so a picker finds a bin by comparing and stepping down. All bin numbers are distinct.

The index arrives as index, a level-order listing. Its first entry is the bin number on the topmost card. After that the listing gives the left then the right card hanging below each card already listed, in the order those cards appear, writing null where no card hangs on that side. Slots below a null are never written down.

Years of insertions have left the index lopsided, so the picker wants it rebuilt to the shallowest shape that still answers lookups the same way. Rebuild it by this rule: take the bin numbers in ascending order, put the middle one on the top card, and rebuild the stretch below it on the left from the numbers before it and the stretch on the right from the numbers after it, applying the same rule to each stretch. When a stretch holds an even count of numbers, the lower of its two middle numbers goes on top.

Return the rebuilt index as a level-order listing in the same form, carrying no trailing null entries.

Examples

Example 1

Input
index = [8, 5, 20, 2, null, null, 40]
Output
[8, 2, 20, null, 5, null, 40]

The bin numbers in ascending order are 2, 5, 8, 20, 40. The middle one is 8, so it stays on the top card, 2 and 5 rebuild the left stretch and 20 and 40 the right one. Each stretch of two takes its lower number on top, giving 2 with 5 hanging right of it and 20 with 40 hanging right of it.

Example 2

Input
index = [4, null, 9, null, 15, null, 22, null, 31]
Output
[15, 4, 22, null, 9, null, 31]

Every card hangs to the right of the one above it, so the index is a single strand of five cards. Ascending, the numbers are 4, 9, 15, 22, 31, and the middle one is 15.

Example 3

Input
index = [6, 4, 9]
Output
[6, 4, 9]

Ascending, the numbers are 4, 6, 9, and the middle one is 6, which is already on the top card with 4 hanging left and 9 hanging right, so the listing comes back unchanged.

Constraints

  • The number of cards in the index is in the range [1, 10^4].
  • 1 <= index[i] <= 10^5 for every slot that holds a card
  • All bin numbers are distinct
  • index[0] is never null
  • index is a valid search index: every card below-and-left carries a smaller bin number and every card below-and-right a larger one

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 rebalance_index(index: list[int | None]) -> list[int | None]:
Java
public Integer[] rebalanceIndex(Integer[] index)

More on the same topics