Technical Interview Question

Given two binary trees s and t, determine if t is a subtree of s. A subtree of a tree s is a tree consisting of a node in s and all of its descendants. The tree s and t could contain duplicates, and the answer should consider the frequency of occurrences of the subtree t.

Write a function to check if t is a subtree of s.

Function Signature:

def isSubtree(s: TreeNode, t: TreeNode) -> bool:

Example

s = [3, 4, 5, 1, 2, None, None, None, None, 0]
t = [4, 1, 2]
Output: True

s = [3, 4, 5, 1, 2, None, None, None, None, 0]
t = [4, 1, None]
Output: False

Answer

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def isSubtree(s: TreeNode, t: TreeNode) -> bool:
    if not s:
        return False
    if isSameTree(s, t):
        return True
    return isSubtree(s.left, t) or isSubtree(s.right, t)

def isSameTree(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 isSameTree(s.left, t.left) and isSameTree(s.right, t.right)

Explanation:

1. Define a helper function isSameTree that checks if two trees are the same by recursively checking if nodes and their children match.
2. In the main function isSubtree, recursively check if the current node of s and t are the same using isSameTree.
3. If they are, return True. If not, move to the left and right subtrees of s and check t there as well.
4. Repeat until the entire s tree is checked. If no matching subtree is found, return False.

The time complexity of this algorithm is O(m*n), where m and n are the number of nodes in trees s and t respectively. The space complexity is O(n) due to the recursive stack space used.