How hard is LeetCode 572. Subtree of Another Tree?

LeetCode 572. Subtree of Another Tree is rated Easy on LeetCode.

What is the time complexity of LeetCode 572. Subtree of Another Tree?

The Python solution on this page runs in O(n \times m).

What is the space complexity of LeetCode 572. Subtree of Another Tree?

The Python solution on this page uses O(n) auxiliary space.

What topics does LeetCode 572. Subtree of Another Tree cover?

LeetCode 572. Subtree of Another Tree is tagged Tree, Depth-First Search, Binary Tree, String Matching and Hash Function on LeetCode.

Subtree of Another Tree — LeetCode 572 Python Solution

EasyTreeDepth-First SearchBinary TreeString MatchingHash Function

Problem: #572
Pattern: Tree Traversal
Reading time: 4 min
Source: leetcode.com

The problem

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.

Example

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

Python solution

Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        def same(p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
            if p is None or q is None:
                return p is q
            return p.val == q.val and same(p.left, q.left) and same(p.right, q.right)

        if root is None:
            return False
        return (
            same(root, subRoot)
            or self.isSubtree(root.left, subRoot)
            or self.isSubtree(root.right, subRoot)
        )

Complexity

Measure	Complexity
Time	O(n \times m)
Space	O(n) auxiliary

Pattern: Tree Traversal

Choose the order — preorder, inorder, postorder, level — and the problem solves itself. LeetCode 572. Subtree of Another Tree is filed here because LeetCode tags it Tree and Binary Tree, which is the vocabulary this hub collects.

The tree traversal guide has the Python template for the pattern and the 225 LeetCode problems that use it.

On study lists

This problem is on Blind 75 and NeetCode 150.

Frequently asked questions

How hard is LeetCode 572. Subtree of Another Tree?: LeetCode 572. Subtree of Another Tree is rated Easy on LeetCode.
What is the time complexity of LeetCode 572. Subtree of Another Tree?: The Python solution on this page runs in O(n \times m).
What is the space complexity of LeetCode 572. Subtree of Another Tree?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 572. Subtree of Another Tree cover?: LeetCode 572. Subtree of Another Tree is tagged Tree, Depth-First Search, Binary Tree, String Matching and Hash Function on LeetCode.