Search in a Binary Search Tree

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

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

def index_branch(index: list, code: int) -> list:

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