v9.1.1
Menu

Subtree of Another Tree

easyPROTrees & BFSAmazon DSA

Given the roots of two binary trees root and subRoot, return True if subRoot is a subtree of root, otherwise False.

Both trees are built from level-order arrays (with None marking a missing child) by the provided build_tree helper, so is_subtree(root, sub_root) receives TreeNode roots, not arrays.

A subtree is a node and all its descendants matching exactly.

Example

Input
3,4,5,1,2
4,1,2
Output
True
Reasoning
  • Inputs: root comes from the level-order array 3,4,5,1,2: 33 is the top node, its children are 44 (left) and 55 (right), and 44 has children 11 and 22. sub_root comes from 4,1,2: a node 44 with children 11 and 22.
  • A subtree of root is not any connected piece of it: it is one node of root together with every node below it, all the way down to the leaves.
  • root has five candidate subtrees, one per node: rooted at 33 (all 5 nodes), at 44 ({4,1,2}\{4, 1, 2\}), and the single leaves 55, 11, 22.
  • The candidate rooted at 44 has value 44 on top, 11 on the left, 22 on the right, and nothing below 11 or 22, which is exactly the shape and values of sub_root. So the answer is True.
  • Notice that the match must be exact to the bottom: if node 22 in root had an extra child 00, the part rooted at 44 would have four nodes, no node of root would match, and the answer would become False.

Constraints

  • 1 <= nodes in root <= 2000
  • 1 <= nodes in subRoot <= 1000
  • -10^4 <= Node.val <= 10^4

More from Amazon DSA

PRO

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Test results

Sign in to run your code against the test cases.