Leetcode – Subtree of Another Tree Solution in Python

Spread the love

Subtree of Another Tree is a classical problem on Leetcode, primarily focusing on binary trees. In this comprehensive article, we shall delve into the Subtree of Another Tree problem, understand the problem statement, and learn how to solve it using various methods in Python.

Problem Statement

Leetcode problem #572 is titled “Subtree of Another Tree” and the problem statement is as follows:

Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree that consists of a node in s and all of this node’s descendants. The tree s could also be considered as a subtree of itself.

Example:

Given tree s:

     3
    / \
   4   5
  / \
 1   2

Given tree t:

   4
  / \
 1   2

Return True, because t has the same structure and node values with a subtree of s.

Definition of Binary Tree Node

Before diving into solving the problem, let’s define the structure of a binary tree node:

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

Approaches to Solve the Problem

1. Recursive Depth-First Search (DFS) Approach

One of the most intuitive ways to solve this problem is through recursion. We can recursively compare each node of tree s with the root of tree t to check if they are identical.

class Solution:
    def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
        if not s:
            return False
        
        # Check if the trees rooted at s and t are identical
        if self.isIdentical(s, t):
            return True
        
        # Recur for left and right subtrees of s
        return self.isSubtree(s.left, t) or self.isSubtree(s.right, t)
    
    def isIdentical(self, s: TreeNode, t: TreeNode) -> bool:
        # Base cases
        if not s and not t:
            return True
        if not s or not t:
            return False
        
        # Check current node and recur for left and right subtrees
        return s.val == t.val and self.isIdentical(s.left, t.left) and self.isIdentical(s.right, t.right)

Explanation:

  1. For each node in tree s, we recursively check if the subtree rooted at this node is identical to tree t by calling isIdentical.
  2. The isIdentical function recursively checks if two trees are identical by comparing the values of their nodes and the structure of the subtrees.

Time Complexity:

The time complexity is O(m * n), where m and n are the number of nodes in trees s and t respectively, as for each node in s, we are checking if a subtree is identical to t.

2. Preorder Traversal with String Matching

Another approach is to serialize both trees using preorder traversal into strings. Then, we can check if the serialized string of tree t is a substring of the serialized string of tree s.

class Solution:
    def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
        def preorder_traversal(node, left_marker=False):
            if not node:
                return 'N' if left_marker else ''
            return f"#{node.val} {preorder_traversal(node.left, True)} {preorder_traversal(node.right)}"
        
        # Serialize the trees
        serialized_s = preorder_traversal(s)
        serialized_t = preorder_traversal(t, True)
        
        # Check if serialized_t is a substring of serialized_s
        return serialized_t in serialized_s

Explanation:

  1. We perform a modified preorder traversal of both trees to serialize them into strings. The left_marker flag helps us differentiate between a None node and an end-of-subtree marker.
  2. We check if the serialized string of tree t is a substring of the serialized string of tree s.

Time Complexity:

The time complexity of this approach is O(m + n + (m – n) * n) = O(mn), where m and n are the number of nodes in trees s and t respectively. The first two terms represent the serialization of the trees, and the last term represents the substring matching.

Conclusion

In this article, we explored two approaches to solve the Subtree of Another Tree problem on LeetCode using Python. The recursive DFS approach is intuitive and easy to understand but has a higher time complexity. The preorder traversal with string matching approach is slightly more optimized but utilizes string manipulation to perform the check.

Leave a Reply