0983EasyTreeDepth-First SearchBreadth-First SearchBinary Tree

Laying One Rig Over Another

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.

Two rigs are given as the flat lists root1 and root2. Each hangs from a single top joint, every joint carries at most two joints below it in a first and a second slot, and either slot may be empty.

A flat list is read level by level: its first entry is the top joint's load, and reading left to right, every entry that is not null claims the next two unused positions as its first and second slot in that order, while null marks an empty slot and claims no positions of its own. A list that ends early leaves the remaining slots empty, and an empty list means no joints at all.

Lay the second rig over the first so their top joints line up, and likewise each pair of matching slots. Where both rigs have a joint, the merged joint carries the two loads added together. Where only one has a joint, that joint and everything below it is kept as it stands.

Return the merged rig in the same flat form, with no null left trailing at the end.

Examples

Example 1

Input: root1 = [1], root2 = [2]
Output: [3]

Both rigs are a single joint, so the merged rig is one joint carrying the two loads added together.

Example 2

Input: root1 = [1], root2 = []
Output: [1]

The second rig has no joints at all, so the first is kept as it stands.

Example 3

Input: root1 = [1, null, 2], root2 = [3, 4]
Output: [4, 4, 2]

The tops add to 4. The first rig has nothing in its first slot, so the second rig's joint there is kept; the second rig has nothing in its second slot, so the first rig's joint there is kept.

Constraints

Each rig holds between 0 and 2000 joints.
0 <= root1.length <= 6000
0 <= root2.length <= 6000
-10000 <= root1[i] <= 10000
-10000 <= root2[i] <= 10000
The first entry of a list is not null unless the list is 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 merge_trees(root1: list, root2: list) -> list:

Java

public Integer[] mergeTrees(Integer[] root1, Integer[] root2)

The intended approach

Time O(a + b) over the two lists' lengths.Space O(a + b) for the slots and the merged rig.

Read each flat list into slots first: walk it level by level, where the filled joints of a level claim the next two positions each, in order, and record for every joint where its two slots sit. That is one pass per rig. Then merge by walking the two rigs together from their tops. With a joint on both sides, the merged joint's load is the two added and its slots are merged in turn. With a joint on one side only, that whole side is copied across untouched. With neither, the slot stays empty. Writing the answer back out means going level by level again: for each level, put out two entries per filled joint of the level above, using `null` for an empty slot, and stop once a level has no filled joints, which is what leaves no trailing nulls.

Pythonentry point: merge_trees

def merge_trees(root1, root2):
    def read(flat):
        if not flat:
            return None, {}, {}
        n = len(flat)
        left = {}
        right = {}
        level = [0]
        at = 1
        while level and at < n:
            nxt = []
            for owner in level:
                if at < n:
                    if flat[at] is not None:
                        left[owner] = at
                        nxt.append(at)
                    at += 1
                if at < n:
                    if flat[at] is not None:
                        right[owner] = at
                        nxt.append(at)
                    at += 1
            level = nxt
        return 0, left, right

    a_root, a_left, a_right = read(root1)
    b_root, b_left, b_right = read(root2)
    # the merged rig, as loads with two slots each
    load = []
    slot1 = []
    slot2 = []

    def fresh(value):
        load.append(value)
        slot1.append(None)
        slot2.append(None)
        return len(load) - 1

    def copy(flat, node, left, right):
        made = fresh(flat[node])
        if node in left:
            slot1[made] = copy(flat, left[node], left, right)
        if node in right:
            slot2[made] = copy(flat, right[node], left, right)
        return made

    def merge(a, b):
        if a is None and b is None:
            return None
        if a is None:
            return copy(root2, b, b_left, b_right)
        if b is None:
            return copy(root1, a, a_left, a_right)
        made = fresh(root1[a] + root2[b])
        slot1[made] = merge(a_left.get(a), b_left.get(b))
        slot2[made] = merge(a_right.get(a), b_right.get(b))
        return made

    top = merge(a_root, b_root)
    if top is None:
        return []
    out = [load[top]]
    level = [top]
    while True:
        chunk = []
        nxt = []
        for node in level:
            for child in (slot1[node], slot2[node]):
                if child is None:
                    chunk.append(None)
                else:
                    chunk.append(load[child])
                    nxt.append(child)
        if not nxt:
            break
        out.extend(chunk)
        level = nxt
    while out and out[-1] is None:
        out.pop()
    return out

The obvious version

Turn each rig into a table keyed by the route down to a joint, spelt out as a run of first and second slot steps. Merging is then adding the two tables together, adding the loads where a route appears in both. Writing the answer out means walking the routes level by level. Goes by routes rather than by slots.

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_merge_trees(root1, root2):
    def table(flat):
        out = {}
        if not flat:
            return out
        n = len(flat)
        route = {0: ""}
        level = [0]
        at = 1
        out[""] = flat[0]
        while level and at < n:
            nxt = []
            for owner in level:
                for step in ("1", "2"):
                    if at >= n:
                        break
                    if flat[at] is not None:
                        route[at] = route[owner] + step
                        out[route[at]] = flat[at]
                        nxt.append(at)
                    at += 1
            level = nxt
        return out

    first = table(root1)
    second = table(root2)
    merged = {}
    for key in first:
        merged[key] = first[key]
    for key in second:
        if key in merged:
            merged[key] = merged[key] + second[key]
        else:
            merged[key] = second[key]
    if "" not in merged:
        return []
    out = [merged[""]]
    level = [""]
    while True:
        chunk = []
        nxt = []
        for key in level:
            for step in ("1", "2"):
                child = key + step
                if child in merged:
                    chunk.append(merged[child])
                    nxt.append(child)
                else:
                    chunk.append(None)
        if not nxt:
            break
        out.extend(chunk)
        level = nxt
    while out and out[-1] is None:
        out.pop()
    return out

How this problem was checked

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