algoadvance

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,None,None,0], subRoot = [4,1,2]
Output: False

Clarifying Questions

1. Are the tree node values guaranteed to be integers?
2. Can either root or subRoot be None?
3. Should we consider that duplicates can exist in the trees?

Code

from typing import Optional

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def isSubtree(root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
    if not subRoot:
        return True  # An empty tree is a subtree of any tree
    if not root:
        return False  # Non-empty tree cannot be a subtree of an empty tree

    if isSameTree(root, subRoot):
        return True

    return isSubtree(root.left, subRoot) or isSubtree(root.right, subRoot)

def isSameTree(s: Optional[TreeNode], t: Optional[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)

Strategy

1. Base Cases:
   • If subRoot is None, then it is a subtree of any tree, thus return True.
   • If root is None and subRoot is not None, then subRoot cannot be a subtree of root, thus return False.
2. Recursive Check for Subtree:
   • Utilize a helper function isSameTree to check if two trees are identical.
   • If isSameTree(root, subRoot) returns True, then subRoot is indeed a subtree of root.
   • Recursive calls to isSubtree to check root.left and root.right.
3. Helper Function isSameTree:
   • Check if both trees are None which means they are identical.
   • If one of the trees is None and the other is not, return False.
   • If values of the current nodes don’t match, return False.
   • Recursively check left and right children.

Time Complexity

• The time complexity of isSameTree is O(n) where n is the number of nodes in the trees being compared.
• Worst-case scenario:
  • Each node in root is checked, and for each node, isSameTree compares potentially m nodes of subRoot.
  • Therefore, the worst-case time complexity is O(N * M), where N is the number of nodes in root and M is the number of nodes in subRoot.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?