0409MediumLinked ListDivide and ConquerTreeBinary Search TreeBinary Tree

Balanced Index Tree From A Reading Chain

Tracked in this browser only

Trains the technique from

LeetCode 109Convert Sorted List to 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 tape archive keeps its readings in one forward chain, already running from smallest to largest. The chain is handed to you as the list chain of its values, first link to last, and equal values may repeat.

Turn the chain into an index tree with this rule, which applies to any stretch of consecutive links:

An empty stretch produces no node.
Otherwise, if the stretch holds k links, the node takes the value at position k // 2 of the stretch, counting positions from 0. The links before that position form its left stretch and the links after it form its right stretch, and each is turned into a subtree by the same rule.

On a stretch of even length the rule therefore takes the upper of the two middle links. Walking the finished tree in order reproduces the chain, and at every node the taller side is ahead of the shorter by at most one level.

Return the tree as a level-order list. The first entry is the root's value; after that every node present contributes its left child and then its right child, writing null for a child that is absent. Nothing beneath an absent child is listed, and null entries at the very end are trimmed. An empty chain produces an empty list.

Examples

Example 1

Input: chain = [2,4,6,8]
Output: [6,4,8,2]

The stretch holds 4 links, so position 4 // 2 = 2 gives the root 6. Links [2,4] go left, and that stretch of 2 takes position 1, namely 4, with 2 hanging on its left. Link [8] goes right on its own.

Example 2

Input: chain = [7]
Output: [7]

A stretch of one link becomes a single node with both children absent, and their two trailing `null` entries are trimmed.

Example 3

Input: chain = [-9,-4,1,3,5,11,20]
Output: [3,-4,11,-9,1,5,20]

Position 7 // 2 = 3 gives the root 3. The stretch [-9,-4,1] yields -4 over -9 and 1, and the stretch [5,11,20] yields 11 over 5 and 20.

Example 4

Input: chain = [10,20]
Output: [20,10]

With 2 links the rule takes position 1, so 20 is the root and 10 becomes its left child. The root's absent right child is a trailing `null` and is trimmed.

Example 5

Input: chain = [1,1,2,2,2]
Output: [2,1,2,1,null,2]

Position 5 // 2 = 2 gives the root 2. The stretch [1,1] yields the second 1 with the first 1 on its left, and the stretch [2,2] yields the second 2 with the other 2 on its left.

Constraints

The number of links in chain is in the range [0, 2 * 10^4].
-10^5 <= chain[i] <= 10^5
chain is given in non-decreasing order.

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 sorted_list_to_b_s_t(chain: list[int]) -> list:

Java

public TreeNode sortedListToBST(ListNode head)

The intended approach

Time O(n)Space O(n) for the nodes and the returned list, with O(log n) nesting

Work on index ranges of the chain rather than on the links themselves. A range picks its node value at the offset the rule names, then hands the part before it and the part after it to the same routine, which builds the whole tree with one node per link. Each call halves its range, so the nesting only reaches about log n. A queue-driven pass over the finished nodes then writes the level-order list, emitting `null` for each absent child and dropping the trailing ones.

Pythonentry point: sorted_list_to_b_s_t

def sorted_list_to_b_s_t(chain):
    # Time O(n): every reading becomes exactly one node, and the level-order
    # write-out visits each node once. Space O(n) for the nodes plus the
    # returned list; the recursion is only O(log n) deep because each call
    # halves the segment it was handed.
    def build(lo, hi):
        if lo > hi:
            return None
        mid = lo + (hi - lo + 1) // 2
        return [chain[mid], build(lo, mid - 1), build(mid + 1, hi)]

    top = build(0, len(chain) - 1)
    if top is None:
        return []
    out = [top[0]]
    ring = [top]
    head = 0
    while head < len(ring):
        node = ring[head]
        head += 1
        for slot in (1, 2):
            child = node[slot]
            if child is None:
                out.append(None)
            else:
                out.append(child[0])
                ring.append(child)
    while out and out[-1] is None:
        out.pop()
    return out

The obvious version

Never build nodes at all: keep a queue of the index ranges that are live on the current frontier, and for each one emit the values its two child ranges would carry, pushing the non-empty ones back on the queue.

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 bf_sorted_list_to_b_s_t(chain):
    n = len(chain)
    if n == 0:
        return []

    def pick(lo, hi):
        return lo + (hi - lo + 1) // 2

    out = [chain[pick(0, n - 1)]]
    queue = [(0, n - 1)]
    head = 0
    while head < len(queue):
        lo, hi = queue[head]
        head += 1
        mid = pick(lo, hi)
        for seg in ((lo, mid - 1), (mid + 1, hi)):
            a, b = seg
            if a > b:
                out.append(None)
            else:
                out.append(chain[pick(a, b)])
                queue.append(seg)
    while out and out[-1] is None:
        out.pop()
    return out

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
5 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