0116EasyTreeDepth-First SearchBinary Tree

Scaffold Stands Steady

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 rigging crew stacks a scaffold from steel joints. One joint sits on the pad, and every joint can carry up to two joints above it: one clamped to its left brace and one clamped to its right brace. Each joint is stamped with a load rating, which runs negative for joints rated in tension.

Because the harness passes plain JSON, the scaffold arrives as the array struts, listed level by level from the pad joint upwards. The first entry is the pad joint's rating, then entries come in pairs giving the left-brace and right-brace joints of the next joint in that same level order. A brace carrying nothing is written null, and a null contributes no pair of its own. An empty array means the crew put up no scaffold at all.

Call the lift of a joint the number of levels in the stack resting on it, counting the joint itself, and the lift of an empty brace zero. The site inspector signs off a scaffold as steady when at every single joint the lift on its left brace and the lift on its right brace are within one of each other. A scaffold that was never put up passes by default.

Return true when the inspector signs off and false when some joint fails the rule.

Examples

Example 1

Input: struts = [7, 3, 9, 1, null, null, 4]
Output: true

Both braces of the pad joint carry two levels, and joints 3 and 9 each carry one level on one brace and nothing on the other, which is within the allowance.

Example 2

Input: struts = [8, 4, null, 2, null, 1]
Output: false

Joint 8 carries three levels on its left brace and nothing on its right, so the lifts differ by three.

Example 3

Input: struts = [1, 2, 3, 4, null, 5, 6, 7, null, 8, null, 9, null]
Output: false

The pad joint looks fine with three levels over each brace, but joint 2 carries two levels on its left brace and nothing on its right, so the failure sits above the pad.

Constraints

The number of joints in the scaffold is in the range [0, 5000].
-10^4 <= struts[i] <= 10^4
Entries that are not `null` are integers; `null` marks a brace carrying nothing.

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 scaffold_stands_steady(struts: list) -> bool:

Java

public boolean scaffoldStandsSteady(Integer[] struts)

The intended approach

Time O(n)Space O(n)

Rebuild the joints, then measure lifts from the top down in a single sweep: each joint asks its two braces for their lifts, compares them, and hands its own lift upward as one more than the larger. A joint whose braces differ by more than one hands back a marker instead of a lift, and every joint below stops measuring and passes the marker along, so the whole scaffold is judged in one traversal.

Pythonentry point: scaffold_stands_steady

def scaffold_stands_steady(struts):
    class Joint:
        __slots__ = ("rating", "left", "right")

        def __init__(self, rating):
            self.rating = rating
            self.left = None
            self.right = None

    if not struts or struts[0] is None:
        return True
    ground = Joint(struts[0])
    level = [ground]
    at = 0
    i = 1
    while at < len(level) and i < len(struts):
        joint = level[at]
        at += 1
        if i < len(struts):
            v = struts[i]
            i += 1
            if v is not None:
                joint.left = Joint(v)
                level.append(joint.left)
        if i < len(struts):
            v = struts[i]
            i += 1
            if v is not None:
                joint.right = Joint(v)
                level.append(joint.right)

    def reach(joint):
        if joint is None:
            return 0
        left = reach(joint.left)
        if left < 0:
            return -1
        right = reach(joint.right)
        if right < 0:
            return -1
        if left - right > 1 or right - left > 1:
            return -1
        return 1 + (left if left > right else right)

    return reach(ground) >= 0

The obvious version

Visit every joint, and for each one measure both brace lifts from scratch with a fresh recursive scan before comparing them. O(n^2).

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_scaffold_stands_steady(struts):
    if not struts or struts[0] is None:
        return True
    ground = {"r": struts[0], "l": None, "u": None}
    level = [ground]
    at = 0
    i = 1
    while at < len(level) and i < len(struts):
        joint = level[at]
        at += 1
        for side in ("l", "u"):
            if i >= len(struts):
                break
            v = struts[i]
            i += 1
            if v is not None:
                joint[side] = {"r": v, "l": None, "u": None}
                level.append(joint[side])

    def reach(joint):
        if joint is None:
            return 0
        a = reach(joint["l"])
        b = reach(joint["u"])
        return 1 + (a if a > b else b)

    stack = [ground]
    while stack:
        joint = stack.pop()
        gap = reach(joint["l"]) - reach(joint["u"])
        if gap > 1 or gap < -1:
            return False
        for side in ("l", "u"):
            if joint[side] is not None:
                stack.append(joint[side])
    return True

How this problem was checked

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