Subtree Of Another Tree - Leetcode Solution

The Subtree Of Another Tree problem on LeetCode asks you to determine if a given binary tree is a subtree of another binary tree.

Here is the problem statement:

Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node's descendants. The tree s could also be considered as a subtree of itself.

Example 1:

Given the following tree s:

     3
    / \
   4   5
  / \
 1   2

Given the following tree t:

   4
  / \
 1   2

Return true, because t has the same structure and node values with a subtree of s.

Example 2:

Given the following tree s:

     3
    / \
   4   5
  / \
 1   2
    /
   0

Given the following tree t:

   4
  / \
 1   2

Return false.

The solution to this problem can be approached using recursion. To check if tree t is a subtree of s, we need to check if tree t is a subtree of both the left and right subtrees of s.

We can define a helper function called isSameTree that checks if two trees are the same. This function can be called recursively to check if the subtree of s at each node is the same as t.

Here is the solution in Python:

class Solution:
    def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
        if not s:
            return False
        if self.isSameTree(s, t):
            return True
        return self.isSubtree(s.left, t) or self.isSubtree(s.right, t)
    
    def isSameTree(self, s: TreeNode, t: TreeNode) -> bool:
        if not s and not t:
            return True
        if not s or not t:
            return False
        if s.val != t.val:
            return False
        return self.isSameTree(s.left, t.left) and self.isSameTree(s.right, t.right)

In the isSubtree function, we first check if s is empty. If s is empty, then t cannot be a subtree of s.

Next, we check if the root nodes of s and t are the same using the isSameTree function. If they are the same, then t is a subtree of s.

If the root nodes of s and t are not the same, then t may be a subtree of the left subtree or the right subtree of s. We recursively call the isSubtree function on the left and right subtrees of s.

In the isSameTree function, we first check if s and t are both empty. If they are both empty, then they are the same.

If one of s or t is empty but the other is not, then they are not the same. If the values of the root nodes of s and t are different, then they are not the same.

If the values of the root nodes of s and t are the same, then we recursively check if their left and right subtrees are the same.

This solution has a time complexity of O(m*n) in the worst case, where m and n are the number of nodes in s and t, respectively. This is because we need to check if t is a subtree of each node in s. However, in practice, the time complexity is much lower because we can usually prune the search early.

1