Subtree of Another Tree easy

Problem Statement

Given the roots of two binary trees root and subRoot, determine if there is a subtree of root that matches subRoot.

A subtree of a tree T is a tree S consisting of a node in T and all of its descendants. A subtree must contain all descendants. For example:

    3
   / \
  4   5
 / \
1   2

is a subtree of:

      1
     / \
    2   3
       / \
      4   5

Example 1

Input: root = [3,4,5,1,2], subRoot = [4,1,2] Output: true

Example 2

Input: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2] Output: false

Steps

  1. Recursive Matching: Create a recursive function isSameTree to check if two given trees are identical. This function compares the nodes' values and recursively checks the left and right subtrees.

  2. Subtree Check: Create a recursive function isSubtree that traverses the root tree. For each node in root, it calls isSameTree to check if the subtree rooted at that node matches subRoot.

  3. Base Cases: In isSameTree, if either tree is empty, they match only if both are empty. In isSubtree, if root is empty, it cannot contain subRoot.

  4. Recursive Calls: If nodes match in isSameTree, continue recursively comparing left and right subtrees. In isSubtree, if a node in root matches the root of subRoot, check for a match using isSameTree. Otherwise, continue recursively traversing root's left and right subtrees.

Explanation

The isSameTree function performs a depth-first comparison of two trees. It efficiently verifies if the structure and values are identical. The isSubtree function systematically explores the root tree, attempting to find a subtree matching subRoot at each node. The recursive nature allows for efficient traversal and comparison without needing to explicitly store or manage the entire tree structure.

Code

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

def isSameTree(p, q):
    if not p and not q:
        return True
    if not p or not q:
        return False
    return p.val == q.val and isSameTree(p.left, q.left) and isSameTree(p.right, q.right)

def isSubtree(root, subRoot):
    if not root:
        return False
    if isSameTree(root, subRoot):
        return True
    return isSubtree(root.left, subRoot) or isSubtree(root.right, subRoot)

#Example Usage
root = TreeNode(3)
root.left = TreeNode(4)
root.right = TreeNode(5)
root.left.left = TreeNode(1)
root.left.right = TreeNode(2)

subRoot = TreeNode(4)
subRoot.left = TreeNode(1)
subRoot.right = TreeNode(2)

print(isSubtree(root, subRoot))  # Output: True


root2 = TreeNode(3)
root2.left = TreeNode(4)
root2.right = TreeNode(5)
root2.left.left = TreeNode(1)
root2.left.right = TreeNode(2)
root2.left.right.left = TreeNode(0)


subRoot2 = TreeNode(4)
subRoot2.left = TreeNode(1)
subRoot2.right = TreeNode(2)

print(isSubtree(root2, subRoot2)) # Output: True


root3 = TreeNode(1)
root3.left = TreeNode(2)
root3.right = TreeNode(3)

subRoot3 = TreeNode(4)
print(isSubtree(root3, subRoot3)) #Output: False

Complexity

  • Time Complexity: O(M * N), where N is the number of nodes in root and M is the number of nodes in subRoot. In the worst case, isSameTree might be called for every node in root.

  • Space Complexity: O(max(N, M)) in the worst case due to the recursive call stack depth, which is proportional to the height of the larger tree.