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.
Top comments (0)