CODING

Day 18: The “Subtree of Another Tree” Problem

Problem:

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 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 1:
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.

Example 2:
Given tree s:

     3
    / \
   4   5
  / \
 1   2
    /
   0

Given tree t:

   4
  / \
 1   2

Return false.

My Solution:

def preorder(self, node: TreeNode):
    if node is None:
        return ""
    left = self.preorder(node.left).strip()
    right = self.preorder(node.right).strip()
    return (" " + str(node.val) + " " 
            + ("null" if left == "" else left)  + " "
            + ("null" if right == "" else right) + " "
    )
def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
    return self.preorder(t) in self.preorder(s)

Explanation:

Let’s try to understand preorder traversal first before we move ahead.

Pre-order traversal is one of the many ways to traverse a tree.

In preorder traversal, we,

1. Visit the root
2. Recursively traverse the left subtree
3. Recursively traverse the right subtree

Let’s take Example 1,

For s, the preorder traversal will happen as illustrated below:

We see that the preorder for s is 34125.

Similarly, for t, the preorder traversal will be like this:

The preorder for t as we see is 412.

We see that, when we do preorder traversal, we process 5 only after process the entire subtree under 4. So, we know, the preorder of the subtree under 4, ie, 412, will be a substring of the entire tree’s preorder.

Therefore, we can conclude that if we have a tree t, it will be a subtree within the tree s only if the preorder of the t is a substring of the preorder of s.

And that’s how we test if a tree is a “Subtree of Another Tree”.

If you are interested in solving more problems, do follow 60 Days of Coding and join me in this journey.

If you would like me to solve and explain any problems, please add them as comments, along with a link to the problem description.

See you tomorrow!

Cheers!