Back

572. Subtree of Another Tree

Easy
Tree
Depth-First Search
String Matching
Binary Tree
Hash Function
Solve on LeetCode View Solutions

Description

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.

 

Example 1:

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

Example 2:

Input: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
Output: false

 

Constraints:

  • The number of nodes in the root tree is in the range [1, 2000].
  • The number of nodes in the subRoot tree is in the range [1, 1000].
  • -104 <= root.val <= 104
  • -104 <= subRoot.val <= 104

Hints

Hint 1
Which approach is better here- recursive or iterative?
Hint 2
If recursive approach is better, can you write recursive function with its parameters?
Hint 3
Two trees <b>s</b> and <b>t</b> are said to be identical if their root values are same and their left and right subtrees are identical. Can you write this in form of recursive formulae?
Hint 4
Recursive formulae can be: isIdentical(s,t)= s.val==t.val AND isIdentical(s.left,t.left) AND isIdentical(s.right,t.right)

Similar Questions

Count Univalue Subtrees
Medium
Most Frequent Subtree Sum
Medium

Statistics

Acceptance
51.0%
Submissions
2,347,783
Accepted
1,197,769