Show problems as
Classic problem #110EasyTreeDepth-First SearchBinary Tree

Balanced Binary Tree

Real-world version: Scaffold Stands Steady
Tracked in this browser only
Read Balanced Binary Tree on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstValidation & Properties · Binary Trees & BST, animated step by step

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

Python
def scaffold_stands_steady(struts: list) -> bool:
Java
public boolean scaffoldStandsSteady(Integer[] struts)

More on the same topics