Subtree of Another Tree — Easy Coding Interview Question

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 as subRoot.

Example

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

Output: true

Constraints

• The number of nodes in root is in [1, 2000]
• The number of nodes in subRoot is in [1, 1000]

Topics & Companies

Topics: trees

Asked by: Amazon, Meta, Microsoft, Google

Optimal Solution Complexity

Time complexity: O(m * n). Space complexity: O(m + n).

Practice more

• All DSA Problems
• DSA Patterns