DEV Community

Harshavardhan
Harshavardhan

Posted on • Edited on

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
Enter fullscreen mode Exit fullscreen mode

For the above tree

   4                   |           4                                
  / \                  |          / 
 3   6                 |         3
                       |
This is a subtree      |       This is not a subtree
                       |        
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

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.

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs