We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Subtree of Another Tree

Difficulty: Easy

Problem Description

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.

Key Insights

  • A subtree matches if the structure and values of the nodes are identical.
  • We need to traverse the main tree and check for matches at each node.
  • A recursive approach can be effective to check subtree equality.

Space and Time Complexity

Time Complexity: O(N * M) where N is the number of nodes in root and M is the number of nodes in subRoot. In the worst case, we may need to check every node in root against every node in subRoot. Space Complexity: O(H) where H is the height of the root tree due to the recursion stack.

Solution

To determine if subRoot is a subtree of root, we can follow these steps:

  1. Traverse the root tree using a depth-first search (DFS).
  2. At each node in root, check if the subtree starting from that node is identical to subRoot.
  3. To check for equality, we will recursively compare the nodes of both trees.
  4. If we find a matching subtree, return true; if we traverse the entire root without finding a match, return false.

Code Solutions

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

def isSameTree(p: TreeNode, q: TreeNode) -> bool:
    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)
← Back to All Questions