Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
Subtree of Another Tree (easy)
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Problem Statement

Given two binary trees s and t, determine if tree t is a subtree of tree s. A tree t is considered a subtree of s if there exists a node in s such that the subtree of that node is identical to t. Both trees are considered identical if their structure and nodes are the same.

Examples

    • Input:
      • Tree s: [3,4,5,1,2]
      • Tree t: [4,1,2]
    • Expected Output: true
    • Justification: Tree t can be found as a subtree of s rooted at the node with value 4.
Image
    • Input:
      • Tree s: [1,2,3]
      • Tree t: [2,3]
    • Expected Output: false
    • Justification: There's no subtree in s that looks like tree t.
Image
    • Input:
      • Tree s: [3,4,5,1,2,null,null,null,null,0]
      • Tree t: [4,1,2]
    • Expected Output: false
    • Justification: Even though there's a subtree with root 4, it's not identical to tree t.
Image

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].
  • -10<sup>4</sup> <= root.val <= 10<sup>4</sup>
  • -10<sup>4</sup> <= subRoot.val <= 10<sup>4</sup>

Try it yourself

Try solving this question here:

Python3
Python3
. . . .

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible