0459EasyTreeBinary Search TreeBinary Tree

Pulling A Branch Out Of A Code Index

Tracked in this browser only

Trains the technique from

LeetCode 700Search in 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 depot keeps its part codes in an ordered index. The index has a head entry, every entry hangs at most two entries below it - one on its low side and one on its high side - and the ordering is strict: every code anywhere below an entry's low side is smaller than that entry's code, and every code anywhere below its high side is larger. No code appears twice.

The index arrives as the array index, written out level by level. index[0] is the head entry's code. The entries after it come in pairs, giving the low side and then the high side of each entry already written out, taken in the same order those entries were written. A side with nothing hanging on it is written null, and a null never claims a pair of its own. Trailing null entries are left off the end.

Return the branch headed by the entry whose code is code, written out in exactly that same convention: the matched code first, then the pairs for the entries of the branch in the order they are written, null for an empty side, and no trailing null entries. Return an empty list if no entry carries code.

Use the ordering to find the entry: the walk down should touch one entry per level, not the whole index.

Examples

Example 1

Input: index = [50, 22, 74, 9, 35, 61, 90, null, null, 30, null, null, null, 82], code = 22
Output: [22, 9, 35, null, null, 30]

The entry holding 22 has 9 on its low side and 35 on its high side; 9 hangs nothing, and 35 carries 30 on its low side and nothing on its high side.

Example 2

Input: index = [50, 22, 74, 9, 35, 61, 90, null, null, 30, null, null, null, 82], code = 90
Output: [90, 82]

The entry holding 90 carries 82 on its low side and nothing on its high side, and the blank for that empty high side falls at the end of the listing so it is left off.

Example 3

Input: index = [50, 22, 74, 9, 35, 61, 90, null, null, 30, null, null, null, 82], code = 47
Output: []

No entry in the index holds 47.

Constraints

1 <= number of entries <= 5000
1 <= code held by an entry <= 10^7
1 <= code <= 10^7
The codes held by the entries are distinct and obey the ordering above.
index[0] is a code, so the index is never empty

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 index_branch(index: list, code: int) -> list:

Java

public List<Integer> indexBranch(Integer[] index, int code)

The intended approach

Time O(n) to rebuild the listing of n entries, then O(h) for the walk down over h levels and O(m) to write out a branch of m entries.Space O(n) for the rebuilt index plus O(m) for the returned branch.

Read the listing once to rebuild each entry's low and high side, which works because the pairs arrive in the order the entries were written. Then start at the head and, at each step, move to the low side when the wanted code is smaller and to the high side otherwise, stopping on a match or on an empty side. Finally sweep the matched entry's branch level by level to write it out, marking empty sides and dropping the blanks that fall at the end.

Pythonentry point: index_branch

def index_branch(index, code):
    if not index or index[0] is None:
        return []
    codes = [index[0]]
    lo = [-1]
    hi = [-1]
    listed = 0
    at = 1
    while listed < len(codes) and at < len(index):
        for slot in range(2):
            if at >= len(index):
                break
            entry = index[at]
            at += 1
            if entry is not None:
                codes.append(entry)
                lo.append(-1)
                hi.append(-1)
                fresh = len(codes) - 1
                if slot == 0:
                    lo[listed] = fresh
                else:
                    hi[listed] = fresh
        listed += 1
    # Follow the ordering down from the head: a smaller code can only be on the
    # low side, a larger one only on the high side. Driven by a loop, not
    # recursion, so a fully lopsided index cannot exhaust the call stack.
    at_node = 0
    while at_node != -1 and codes[at_node] != code:
        at_node = lo[at_node] if code < codes[at_node] else hi[at_node]
    if at_node == -1:
        return []
    # Write the branch back out in the same listing convention.
    out = [codes[at_node]]
    queue = [at_node]
    head = 0
    while head < len(queue):
        node = queue[head]
        head += 1
        for kid in (lo[node], hi[node]):
            if kid == -1:
                out.append(None)
            else:
                out.append(codes[kid])
                queue.append(kid)
    while out and out[-1] is None:
        out.pop()
    return out

The obvious version

Ignore the ordering: scan every rebuilt entry for the code, then give each entry of the branch a seat number, 2k+1 and 2k+2 for the two sides of seat k, and read the seats off in numerical order to build the listing. O(n) for the scan and O(m log m) for the seats, so with the rebuild dominating both it is not asymptotically slower than the reference - it is an independent check, not a slower baseline.

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_index_branch(index, code):
    if not index or index[0] is None:
        return []
    codes = [index[0]]
    lo = [-1]
    hi = [-1]
    listed = 0
    at = 1
    while listed < len(codes) and at < len(index):
        for slot in range(2):
            if at >= len(index):
                break
            entry = index[at]
            at += 1
            if entry is not None:
                codes.append(entry)
                lo.append(-1)
                hi.append(-1)
                fresh = len(codes) - 1
                if slot == 0:
                    lo[listed] = fresh
                else:
                    hi[listed] = fresh
        listed += 1
    found = -1
    for i in range(len(codes)):
        if codes[i] == code:
            found = i
            break
    if found == -1:
        return []
    seat = {}
    stack = [(found, 0)]
    while stack:
        node, pos = stack.pop()
        seat[pos] = codes[node]
        if lo[node] != -1:
            stack.append((lo[node], 2 * pos + 1))
        if hi[node] != -1:
            stack.append((hi[node], 2 * pos + 2))
    taken = sorted(seat)
    out = [seat[0]]
    for pos in taken:
        out.append(seat.get(2 * pos + 1))
        out.append(seat.get(2 * pos + 2))
    while out and out[-1] is None:
        out.pop()
    return out

How this problem was checked

Reference solution executed against 15 test cases — 15 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