deepSWE.io

Subtree of Another Tree

TreeDFSRecursion

15 min

Problem Statement

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

Example 1:

root:

subRoot:

Output: true

Constraints

The number of nodes in the root tree is in the range [1, 2000].
The number of nodes in the subRoot tree is in the range [1, 1000].
-10⁴ ≤ root.val ≤ 10⁴
-10⁴ ≤ subRoot.val ≤ 10⁴

Solution (DFS)

The solution uses a Depth-First Search (DFS) to traverse the main tree. For each node in the main tree, we check if the subtree rooted at that node is identical to the subRoot tree.

Algorithm Steps

Traverse the root tree.
For each node in root, check if the subtree rooted at that node is the same as the subRoot tree.
To check if two trees are the same, we can use a helper function that recursively compares the nodes of the two trees.
If we find a matching subtree, we return true.
If we traverse the entire root tree and don't find a matching subtree, we return false.

Start: Check if subRoot is a subtree of root.

Subtree of Another Tree Solution


# 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
class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        # If the main tree is empty, the subtree cannot exist.
        if not root:
            return False
        # If the current node of the main tree forms the same tree as the subRoot, we've found it.
        if self.isSameTree(root, subRoot):
            return True
        # Otherwise, check if the subRoot exists in the left or right children of the main tree.
        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)

    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        # If both nodes are null, they are the same.
        if not p and not q:
            return True
        # If one node is null, or their values are different, they are not the same.
        if not p or not q or p.val != q.val:
            return False
        # Recursively check if the left and right subtrees are the same.
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)