Show problems as
Classic problem #572EasyTreeDepth-First SearchString MatchingBinary TreeHash Function

Subtree of Another Tree

Real-world version: Does the Rig Hold This Section
Tracked in this browser only
Read Subtree of Another 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

Two cargo rigs are given as the flat lists rig and section. 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.

Return whether some joint of rig, taken together with everything hanging below it, matches section exactly: the same shape, slot for slot, and the same loads throughout.

Examples

Example 1

Input
rig = [1, 2, 3, 4, 5], section = [2, 4, 5]
Output
true

The joint loaded 2 carries 4 in its first slot and 5 in its second, which is exactly the section asked about.

Example 2

Input
rig = [1, 2], section = [1]
Output
false

The section is a single bare joint loaded 1, but the rig's only joint loaded 1 carries another joint below it, so the shapes differ.

Example 3

Input
rig = [7], section = [7]
Output
true

The whole rig is itself a single bare joint matching the section.

Constraints

  • 1 <= rig.length <= 6000
  • 1 <= section.length <= 3000
  • -10000 <= rig[i] <= 10000
  • -10000 <= section[i] <= 10000
  • The first entry of each list is not null.

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 is_subtree(rig: list, section: list) -> bool:
Java
public boolean isSubtree(Integer[] rig, Integer[] section)

More on the same topics