Check if a binary tree is a subtree of another binary tree

Everything which is a descendant of a tree is known as a subtree.
A binary tree(s) is said to be a subtree of another binary tree(t) if s is a descendant of t and follows exact order same as in s. The tree t could also be considered as a subtree of itself.

    7
   / \
  4   8
 / \
3  6

For the above tree

   4                   |           4                                
  / \                  |          / 
 3   6                 |         3
                       |
This is a subtree      |       This is not a subtree
                       |        

---

If you're curious to solve this problem before checking out the solution. Try it out in Leetcode 😉 .

You can find my solutions to other leetcode problems at https://github.com/harsha-sam/Leetcode-Solutions.

---

Solution

I'll be using the boilerplate code from leetcode. You can directly submit the solution and verify, once you understand how the algorithm works.

Comparing Nodes Approach:

• Depth-First Search the tree T and whenever you find a node that has the same value as the root node of the tree S, Compare both tree T and S from this corresponding node of T and check for equality by comparing all nodes of both trees.

# 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, s: TreeNode, t: TreeNode) -> bool:
        '''
        Depth first searches both trees and compares 
        all nodes. 
        Returns False whenever two different nodes 
        encountered
        Returns True when both trees are completely 
        explored and equal.
        '''
        def check_equal(tree1, tree2):
            if tree1 and not tree2 or tree2 and not tree1:
                return False
            elif tree1 and tree2:
                if tree1.val != tree2.val:
                    return False
                if not check_equal(tree1.left, tree2.left):
                    return False
                if not check_equal(tree1.right, tree2.right):
                    return False
            return True

        def explore(curr, t):
            if curr:
                # if a node which has same value as root s is encountered, we check for quality
                if curr.val == t.val and check_equal(curr, t):
                    return True
                if explore(curr.left, t):
                    return True
                if explore(curr.right, t):
                    return True

        return explore(s, t)

---

Time Complexity: O(N * M) - Where M = number of nodes in subtree t and N = number of nodes in tree s
Space Complexity: O(N) - Depth in recursion can go upto n nodes. n refers to number of nodes in s.