Solution: Subtree of Another Tree
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]
 Tree
 Expected Output: true
 Justification: Tree
t
can be found as a subtree ofs
rooted at the node with value 4.
 Input:

 Input:
 Tree
s
: [1,2,3]  Tree
t
: [2,3]
 Tree
 Expected Output: false
 Justification: There's no subtree in
s
that looks like treet
.
 Input:

 Input:
 Tree
s
: [3,4,5,1,2,null,null,null,null,0]  Tree
t
: [4,1,2]
 Tree
 Expected Output: false
 Justification: Even though there's a subtree with root 4, it's not identical to tree
t
.
 Input:
Solution
The central idea is to traverse through each node in tree s
and for every node, attempt to match its subtree with tree t
. If at any node, the subtree rooted at that node matches tree t
, we have found our subtree, and we return true. If no such subtree is found after examining all nodes of s
, we return false.

Traversal and Comparison:
 As we traverse tree
s
, for every node, we try to see if the subtree rooted at that node matches treet
. To do this, we recursively compare nodes from the current subtree ofs
with treet
.
 As we traverse tree

Main Logic:
 We begin by checking if the current node of
s
matches the root oft
. If so, we invoke the matching operation. If they turn out to be identical, then treet
is indeed a subtree ofs
rooted at the current node, and we return true.  If not, we continue the traversal by moving to the left and right children of the current node in
s
.
 We begin by checking if the current node of

Matching Operation:
 This operation checks if two trees are identical. We recursively compare nodes, starting from the given nodes in
s
andt
. If the values of nodes being compared don't match, or if the tree structures differ, we return false. If all nodes match and the structures are identical, we return true.
 This operation checks if two trees are identical. We recursively compare nodes, starting from the given nodes in
Algorithm Walkthrough
Given Tree s
: [3,4,5,1,2] and Tree t
: [4,1,2]
 Start at the root of
s
(value 3)s
value doesn't matcht
root, so continue traversal.
 Move to the left child of
s
(value 4) Now the value matches
t
root. Compare left child of this node in
s
(value 1) with left child oft
root (value 1). They match.
 Compare right child of this node in
s
(value 2) with right child oft
root (value 2). They match.
 Compare left child of this node in
 Now the value matches
 Since both subtrees match, return true.
Code
Python3
Python3
. . .
You must run your code first
Complexity Analysis

Time Complexity:
 In the worst case, we'll be checking each node of
s
to see if it's a subtree that matchest
.  For each node of
s
, in the worst case, we'll be comparing it with each node oft
.  Thus, the worstcase time complexity is O(m * n), where m is the number of nodes in
s
and n is the number of nodes int
.
 In the worst case, we'll be checking each node of

Space Complexity:
 The space complexity is O(m) due to the recursion stack, where m is the depth of tree
s
.
 The space complexity is O(m) due to the recursion stack, where m is the depth of tree