0402EasyTreeDepth-First SearchBreadth-First SearchBinary Tree

Mirror The Splitter Harness

Tracked in this browser only

Trains the technique from

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 cable installer describes a broadcast harness as a binary tree of splitters, where each splitter has a left feed and a right feed and either may be absent.

The harness arrives as a level-order list root. Its first entry is the value at the top splitter. After that, every splitter that is present contributes its left feed and then its right feed, with null written for a feed that is absent. Nothing below an absent feed is listed, and null entries at the very end of the list are trimmed off. An empty harness is the empty list.

Rewire the harness so that at every splitter the left feed and the right feed trade places, and return the rewired harness written in the same level-order form.

Perform the rewiring by swapping the two feed links on each splitter in place. Do not assemble a second harness alongside the first.

Examples

Example 1

Input: root = [8,3,10,1,6,null,14]
Output: [8,10,3,14,null,6,1]

At the top splitter, 3 and 10 trade places. Splitter 3 held feeds 1 and 6, which trade to 6 and 1. Splitter 10 held an absent left feed and 14, which trade to 14 and absent.

Example 2

Input: root = [5,null,9]
Output: [5,9]

Splitter 5 has only a right feed of 9, so after the trade 9 becomes its left feed and its right feed is absent. The trailing `null` for that absent feed is trimmed.

Example 3

Input: root = [6,null,2,3]
Output: [6,2,null,null,3]

Splitter 6 has only a right feed of 2, which becomes its left feed. Splitter 2 has only a left feed of 3, which becomes its right feed.

Example 4

Input: root = [-4]
Output: [-4]

The single splitter has two absent feeds, and trading two absent feeds changes nothing.

Example 5

Input: root = [1,2,null,3]
Output: [1,null,2,null,3]

Splitter 1 keeps only 2, which moves to its right feed. Splitter 2 keeps only 3, which likewise moves to its right feed, so the chain now leans right the whole way down.

Constraints

The number of splitters is in the range [0, 100].
-100 <= splitter value <= 100

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 invert_tree(root: list) -> list:

Java

public TreeNode invertTree(TreeNode root)

The intended approach

Time O(n) where n is the number of splittersSpace O(n) for the assembled splitters, the stack and the returned list

Assemble the splitters from the level-order list with a queue, then drive an explicit stack over every splitter and swap its two feed links in place, pushing whatever the two links now point at. An explicit stack keeps the walk safe on a harness that runs 100 splitters deep in one line. Finally write the same nodes back out in level-order form, emitting `null` for each absent feed and trimming the trailing ones.

Pythonentry point: invert_tree

def _assemble(data):
    if not data or data[0] is None:
        return None
    top = [data[0], None, None]
    ring = [top]
    head = 0
    at = 1
    while head < len(ring) and at < len(data):
        node = ring[head]
        head += 1
        for slot in (1, 2):
            if at >= len(data):
                break
            value = data[at]
            at += 1
            if value is not None:
                node[slot] = [value, None, None]
                ring.append(node[slot])
    return top


def _flatten(top):
    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


def invert_tree(root):
    # Time O(n): assembling, swapping and flattening each touch every splitter
    # once. Space O(n) for the assembled nodes plus the returned list.
    top = _assemble(root)
    stack = [top]
    while stack:
        node = stack.pop()
        if node is None:
            continue
        node[1], node[2] = node[2], node[1]
        stack.append(node[1])
        stack.append(node[2])
    return _flatten(top)

The obvious version

Assemble the splitters, then build a brand new harness recursively where each node's children come from mirroring the original's right feed first and its left feed second, and write that out.

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 _assemble(data):
    if not data or data[0] is None:
        return None
    top = [data[0], None, None]
    ring = [top]
    head = 0
    at = 1
    while head < len(ring) and at < len(data):
        node = ring[head]
        head += 1
        for slot in (1, 2):
            if at >= len(data):
                break
            value = data[at]
            at += 1
            if value is not None:
                node[slot] = [value, None, None]
                ring.append(node[slot])
    return top


def _flatten(top):
    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


def bf_invert_tree(root):
    def mirrored(node):
        if node is None:
            return None
        return [node[0], mirrored(node[2]), mirrored(node[1])]

    return _flatten(mirrored(_assemble(root)))

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