Subtree of Another Tree

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.

Question

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:

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.


Given tree s:

     3
    / \
   4   5
  / \
 1   2
    /
   0
Given tree t:
   4
  / \
 1   2
Return false.

Analyzation

Recursion

This is a very classical problem for recursion. It needs two recursions. One is considering the comparison of two trees and comparison of left subtree or right subtree of s with t.

If s is None and t is None, return True. If t is None and s.val does not equal to t.val, return False. Compare left subtrees and right subtrees till the end.

If s and t has the same val and their subtrees are all equal, meaning it is True. Otherwise, compare the s.left with t and s.right with t.

The Code

class Solution:
    """
    @param s: the s' root
    @param t: the t' root
    @return: whether tree t has exactly the same structure and node values with a subtree of s
    """
    def isSubtree(self, s, t):
        # Write your code here
        if s is None:
            return t is None
        if s.val == t.val and self.compare(s, t):
            return True
        
        return self.isSubtree(s.left, t) or self.isSubtree(s.right, t)
        
    
    def compare(self, s, t):
        if s is None:
            return t is None
        if t is None or s.val != t.val:
            return False
            
        return self.compare(s.left, t.left) and self.compare(s.right, t.right)

Time & Space Complexity

• Time complexity: O(n). Remember that the best case of a Binary Tree is O(logn) since it is a balanced tree but the worst case is O(n) because it can skew to only one side.
• Space complexity: O(n). Remember that the space complexity is always about how many nodes there are in a Binary Tree. If the tree is well-balanced then it is O(logn) but the worst case will be O(n).