Check if a Binary Tree is a Subtree of another Binary Tree
Data Structures and Algorithms Note
Published in
2 min readJan 30, 2022
To identify whether tree 2 is a subtree of tree 1, first we need to consider how to compare whether two trees are the same.
def sametree(self, t1, t2):
# it is equal if tree both are None
if t1 is None and t2 is None:
return True # if both trees are not None:
if t1 and t2 and t1.data == t2.data: # check the rest of nodes in tree are same data as well
return(self.sametree(t1.left, t2.left) and
self.sametree(t1.right, t2.right)) # it is not equal if one tree is None and another is not
# or t1.data and t2.data not the same
return False
since we could identify two trees are the same or not, we could implement into identify one tree is a subtree of another or not.
def subtree(self, t1, t2):
# None is always a subtree of anyother tree
if t2 is None:
return True # if t2 is not None, but t1 is None, they shouldn't be equal
# until go through all the nodes in t1, t1 becomes to None too
if t1 is None:
return False if self.sametree(t1, t2):
return True # if start from current node is not the same tree
# go node.left as root or node.right to check if they are same
return(self.subtree(t1.left, t2) or self.subtree(t1.right, t2))
