Subtree of Another Tree

Patrick Leaton
Published: April 5, 2021, 6:22 a.m.
Problem Description

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.

 

The description was taken from https://leetcode.com/problems/subtree-of-another-tree/.

Problem Solution

#O(S*T) Time, O(N) Space
class Solution:
    def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
        if s is None:
            return False
        elif self.isSameTree(s, t):
            return True
        else:
            return self.isSubtree(s.left, t) or self.isSubtree(s.right, t)
       
    def isSameTree(self, s: TreeNode, t: TreeNode) -> bool:
        if s is None or t is None:
            return not s and not t
        elif s.val == t.val:
            return self.isSameTree(s.left, t.left) and self.isSameTree(s.right, t.right)
        else:
            return False

Problem Explanation

This problem is a variation of Same Tree.

What would make two subtrees different is if the node values were different or if the same nodes have different heights.

To solve this problem, we could utilize two functions.  The first function would recurse the first tree and try to find the subtree that is the same as the given subtree by passing a node from both trees into a second function which will validate their similarities.  If they are not the same, then the first function will instead recurse the child nodes and compare them to the subtree root.  If the first function tries each node from the first tree and didn't find a valid subtree, it will return false overall.

Let's start off by creating our helper function that compares two input nodes from both trees to check if they are equal before recursing their children.

    def isSameTree(self, s: TreeNode, t: TreeNode) -> bool:

 

In this function, we will first check if an input node from the function call is null.

If one is, then we will need to see if both nodes are null so that they’d still be equal.  This statement will return false if this isn't the case.

        if s is None or t is None:
            return s is None and t is None

 

Next, we will see if the call's two input nodes have the same value.

If they do, then we will recursively call this function on their children to validate all of the children are true as well. 

If all the children are equal, then this statement will return true and the initial call from the other function will return true as well since we have found a valid subtree.

        elif s.val == t.val:
            return self.isSameTree(s.left, t.left) and self.isSameTree(s.right, t.right)

 

If a call's two input nodes are not equal, we will return false.

        else:
            return False

Let's now go back to begin working on our isSubtree function.

We will first check if the current node we’re checking the input subtree against is null.  We'll return false if it is.

        if s is None:
            return False

 

Next, we will check if the entirety of the call's input tree and the subtree is the same by passing them to the helper function.

        elif self.isSameTree(s, t):
            return True

 

If not, we will recurse this isSubtree function on both children of the node in the current call, until we find a valid subtree or have traversed the entire tree.

        else:
            return self.isSubtree(s.left, t) or self.isSubtree(s.right, t)