← all entries
A-051● Day 512026.06.26easyleetcode #572neetcode150

Subtree of Another Tree

#tree#depth-first-search#string-matching#binary-tree#hash-function
↗ leetcode #572 · subtree-of-another-tree
01

Problem

· problem
P.051

Subtree of Another Tree

↗ leetcode #572

Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise. A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node's descendants. The tree tree could also be considered as a subtree of itself.

constraints
  • · 1 ≤ nodes in root ≤ 2000
  • · 1 ≤ nodes in subRoot ≤ 1000
  • · -10^4 ≤ node values ≤ 10^4
// paraphrased summary — see source for full text
examples
example 1input → output
[3,4,5,1,2]
[4,1,2]
true
example 2input → output
[3,4,5,1,2,null,null,null,null,0]
[4,1,2]
false
02

Pre-solve

· pre-solve
● 1list shown→● 2select→● 3reveal
  • ☐
    If subRoot is null, should we return true?
  • ☐
    Does the subtree need to start at the root of the main tree?
  • ☐
    If root = [4,1,2] and subRoot = [4,1,2], is subRoot a subtree of root?
  • ☐
    Is [1,2] a subtree of [4,1,2] if both contain values 1 and 2?
  • ☐
    Is it enough to check if root.val == subRoot.val for the root node?
  • ☐
    Can we find subRoot by checking if its values appear in root in any order?
check the items you would ask, then press confirm
// session-only state — refresh resets (repeatable practice)
03

Logic Structure

· logic
● 1slots shown→● 2pick per slot→● 3reveal
// pick one code line per slot to assemble the algorithm flow. no typing — just the logic skeleton.
step 1· Empty subRoot check
○
if not subRoot:
○
if subRoot: return True
○
if not subRoot: pass
step 2· Empty root check
○
if not root:
○
if not root: return True
○
if root and not subRoot: return False
step 3· Check if current subtree matches
○
if self.isSameTree(root, subRoot):
○
if root.val == subRoot.val:
○
if self.isSubtree(root, subRoot):
step 4· Recursively search left and right children
○
return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)
○
return self.isSubtree(root.left, subRoot) and self.isSubtree(root.right, subRoot)
○
return self.isSubtree(root, subRoot.left) or self.isSubtree(root, subRoot.right)
pick one option per slot
// format: slot — recursive / DP patterns use ordering / state-first formats. ADR-08 follow-up.
04

Solve · Trace

· solve
solution.py
1
# Definition for a binary tree node.
2
# class TreeNode:
3
#     def __init__(self, val=0, left=None, right=None):
4
#         self.val = val
5
#         self.left = left
6
#         self.right = right
7
class Solution:
8
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
9
        if not subRoot:
10
            return True
11
        if not root:
12
            return False
13
14
        if self.isSameTree(root, subRoot):
15
            return True
16
        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)
17
18
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
19
        if not p and not q:
20
            return True
21
        if p and q and p.val == q.val:
22
            return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
23
        else:
24
            return False
mental dry-run cases
// walk each case in your head; expand the worked example below if stuck.
case 1
[3,4,5,1,2]
[4,1,2]
→
true
case 2
[3,4,5,1,2,null,null,null,null,0]
[4,1,2]
→
false
// UI does not walk-through — you do the dry-run mentally. Expand the worked example if stuck.