0647MediumDivide and ConquerGreedyTreeDepth-First SearchBinary Search TreeBinary Tree

Rebalancing the Bin Index

Tracked in this browser only

Trains the technique from

LeetCode 1382Balance a Binary Search Tree

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def rebalance_index(index: list[int | None]) -> list[int | None]:

Java

public Integer[] rebalanceIndex(Integer[] index)

The intended approach

Time O(n) for n listed slots: the wiring sweep, the in-order walk, the rebuild and the level sweep each touch a card a constant number of times.Space O(n) for the child tables, the ordered numbers and the stacks, plus the returned listing.

Wire the listing into child tables with a queue sweep, then read the bin numbers off with an in-order walk driven by an explicit stack. Because the listing is a search index, that walk already yields the numbers in ascending order, so no sorting is needed. Rebuild with a second explicit stack whose frames each hold a slice of the ordered numbers plus the card the slice hangs under and on which side, taking the lower middle of each slice as its top card. Finally sweep the rebuilt cards level by level, writing null for an absent card and dropping the trailing run of nulls.

Pythonentry point: rebalance_index

def _decode(listing):
    """Compact level-order listing -> (values, left, right) index tables."""
    if not listing or listing[0] is None:
        return [], [], []
    below_left = [-1] * len(listing)
    below_right = [-1] * len(listing)
    queue = [0]
    head = 0
    slot = 1
    while head < len(queue) and slot < len(listing):
        here = queue[head]
        head += 1
        if slot < len(listing):
            if listing[slot] is not None:
                below_left[here] = slot
                queue.append(slot)
            slot += 1
        if slot < len(listing):
            if listing[slot] is not None:
                below_right[here] = slot
                queue.append(slot)
            slot += 1
    return listing, below_left, below_right


def _encode(root, kids):
    """(root, {node: (leftKid, rightKid)}) -> compact level-order listing."""
    if root is None:
        return []
    out = [root[0]]
    rank = [root]
    head = 0
    while head < len(rank):
        here = rank[head]
        head += 1
        for side in (0, 1):
            child = kids[here][side]
            if child is None:
                out.append(None)
            else:
                out.append(child[0])
                rank.append(child)
    # a trailing run of empty slots carries no information
    while out and out[-1] is None:
        out.pop()
    return out

def rebalance_index(index):
    # the listing is a search index, so an in-order walk already yields ascending
    # bin numbers and no sort is needed
    values, below_left, below_right = _decode(index)
    if not values:
        return []
    ordered = []
    stack = []
    here = 0
    while stack or here != -1:
        while here != -1:
            stack.append(here)
            here = below_left[here]
        here = stack.pop()
        ordered.append(values[here])
        here = below_right[here]

    # rebuild with an explicit stack: each frame is a slice plus where to hang it
    nodes = [(v,) for v in ordered]
    kids = {node: [None, None] for node in nodes}
    root = None
    frames = [(0, len(ordered) - 1, None, 0)]
    while frames:
        lo, hi, owner, side = frames.pop()
        if lo > hi:
            continue
        mid = (lo + hi) // 2
        node = nodes[mid]
        if owner is None:
            root = node
        else:
            kids[owner][side] = node
        frames.append((lo, mid - 1, node, 0))
        frames.append((mid + 1, hi, node, 1))
    return _encode(root, kids)

The obvious version

Ignore the search-index property entirely: gather every bin number with a plain walk, sort them, then build the balanced index by straightforward recursion on slice bounds. Pays for a sort the in-order walk does not need, and recurses instead of using a stack, but it applies the stated rule literally.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def _decode(listing):
    """Compact level-order listing -> (values, left, right) index tables."""
    if not listing or listing[0] is None:
        return [], [], []
    below_left = [-1] * len(listing)
    below_right = [-1] * len(listing)
    queue = [0]
    head = 0
    slot = 1
    while head < len(queue) and slot < len(listing):
        here = queue[head]
        head += 1
        if slot < len(listing):
            if listing[slot] is not None:
                below_left[here] = slot
                queue.append(slot)
            slot += 1
        if slot < len(listing):
            if listing[slot] is not None:
                below_right[here] = slot
                queue.append(slot)
            slot += 1
    return listing, below_left, below_right


def _encode(root, kids):
    """(root, {node: (leftKid, rightKid)}) -> compact level-order listing."""
    if root is None:
        return []
    out = [root[0]]
    rank = [root]
    head = 0
    while head < len(rank):
        here = rank[head]
        head += 1
        for side in (0, 1):
            child = kids[here][side]
            if child is None:
                out.append(None)
            else:
                out.append(child[0])
                rank.append(child)
    # a trailing run of empty slots carries no information
    while out and out[-1] is None:
        out.pop()
    return out

def bf_rebalance_index(index):
    values, below_left, below_right = _decode(index)
    if not values:
        return []
    # ignore the search-index property: gather every bin number, then sort
    seen = []
    stack = [0]
    while stack:
        here = stack.pop()
        if here == -1:
            continue
        seen.append(values[here])
        stack.append(below_left[here])
        stack.append(below_right[here])
    ordered = sorted(seen)

    nodes = [(v,) for v in ordered]
    kids = {node: [None, None] for node in nodes}

    def grow(lo, hi):
        if lo > hi:
            return None
        mid = (lo + hi) // 2
        node = nodes[mid]
        kids[node][0] = grow(lo, mid - 1)
        kids[node][1] = grow(mid + 1, hi)
        return node

    return _encode(grow(0, len(ordered) - 1), kids)

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in