Skip to content
BASA DSA

Subtree of Another Tree

EasyTrees

Return whether root contains a node whose entire rooted subtree has the same structure and values as subRoot.

Example 1

Argument 1 tree: level-order input; omitted children are null.Argument 1 tree: level-order input; omitted children are null. Vertices: node 0: 5, node 1: 3, node 2: 8, node 3: 1, node 4: 4. Edges: node 0 (5) — node 1 (3) left child; node 0 (5) — node 2 (8) right child; node 1 (3) — node 3 (1) left child; node 1 (3) — node 4 (4) right child.53814
Argument 1 tree: level-order input; omitted children are null.

Argument 2 tree: level-order input; omitted children are null.Argument 2 tree: level-order input; omitted children are null. Vertices: node 0: 3, node 1: 1, node 2: 4. Edges: node 0 (3) — node 1 (1) left child; node 0 (3) — node 2 (4) right child.314
Argument 2 tree: level-order input; omitted children are null.

Input
root = [5,3,8,1,4]
subRoot = [3,1,4]
Output
true

Explanation

The entire subtree rooted at 3 matches [3,1,4].

Example 2

Argument 1 tree: level-order input; omitted children are null.Argument 1 tree: level-order input; omitted children are null. Vertices: node 0: 5, node 1: 3, node 2: 8, node 3: 1, node 4: 4, node 5: 0. Edges: node 0 (5) — node 1 (3) left child; node 0 (5) — node 2 (8) right child; node 1 (3) — node 3 (1) left child; node 1 (3) — node 4 (4) right child; node 3 (1) — node 5 (0) left child.538140
Argument 1 tree: level-order input; omitted children are null.

Argument 2 tree: level-order input; omitted children are null.Argument 2 tree: level-order input; omitted children are null. Vertices: node 0: 3, node 1: 1, node 2: 4. Edges: node 0 (3) — node 1 (1) left child; node 0 (3) — node 2 (4) right child.314
Argument 2 tree: level-order input; omitted children are null.

Input
root = [5,3,8,1,4,null,null,0]
subRoot = [3,1,4]
Output
false

Explanation

The candidate subtree has an extra descendant 0; matching its first values is insufficient.

Example 3

Argument 1 tree: level-order input; omitted children are null.Argument 1 tree: level-order input; omitted children are null. Vertices: node 0: 2. Edges: none.2
Argument 1 tree: level-order input; omitted children are null.

Argument 2 tree: level-order input; omitted children are null.Argument 2 tree: level-order input; omitted children are null. Vertices: node 0: 2. Edges: none.2
Argument 2 tree: level-order input; omitted children are null.

Input
root = [2]
subRoot = [2]
Output
true

Explanation

A tree is a subtree of itself, including this singleton.

Constraints

  • 1 <= nodes in each tree <= 2000
  • Trees are breadth-first arrays with null holes

Function contractisSubtreeArguments: tree, tree
Loading draft…
SolutionRuns on your device