Facebook PixelSubtree of Another Tree — Coding Practice
Subtree of Another TreeEasy

Subtree of Another Tree

Easy 7.3k46% acceptance
TreeDepth-First SearchBinary TreeString Matching

Given the roots of two binary trees root and subRoot, return true if root contains a subtree whose shape and node values exactly match subRoot, and false otherwise.

A subtree of a tree is any node in that tree together with all of its descendants. The whole tree counts as a subtree of itself.

Both trees are given in level-order (TreeNode with { val, left, right }, null for a missing child).

Example 1
Input: root = [3,4,5,1,2], subRoot = [4,1,2]
Output: true
The node 4 and its children 1 and 2 form a subtree identical to subRoot.
Example 2
Input: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
Output: false
The matching 4-node now has an extra descendant, so it no longer equals subRoot exactly.
Example 3
Input: root = [1,1], subRoot = [1]
Output: true
Constraints
  • The number of nodes in `root` is in the range [1, 2000].
  • The number of nodes in `subRoot` is in the range [1, 1000].
  • -10⁴ ≤ Node.val ≤ 10⁴
Asked atAmazonMicrosoftMetaApple
JavaScript
Loading editor…
Case 1
[3,4,5,1,2], [4,1,2]
expected: true
Case 2
[3,4,5,1,2,null,null,null,null,0], [4,1,2]
expected: false
Case 3
[1,1], [1]
expected: true
Case 4
[1,2,3], [4]
expected: false
Case 5
[3,4,5,1,2], [3,4,5,1,2]
expected: true
Case 6
[1], [1]
expected: true
Case 7
[1,2], [2]
expected: true