Is Subtree

Check if a subtree is a subtree of a given tree

Solution 1

Two helper functions are needed:

1) One that is called for each node of the tree that checks if starting at this node, the subtree in argument is equivalent to the subtree starting at this node

2) A second one called inside the first one that checks if the values of the node of the current of tree and subtree are equivalent and check recursively the following nodes

# Solution 1
def isSubtree(root: Optional[TreeNode], subroot: Optional[TreeNode]) -> bool:
    def helper_equal(root, subroot):
        if not (root and subroot):
            return root is subroot
        return(root.val==subroot.val and
               helper_equal(root.left, subroot.left) and
               helper_equal(root.right, subroot.right))

    def helper_is_subtree(root, subroot):
        if helper_equal(root, subroot):
            return True
        if not root:
            return(False)
        return(helper_is_subtree(root.left, subroot) or helper_is_subtree(root.right, subroot))

    return(helper_is_subtree(root, subroot))

Solution 2-and-O(S%2BT)-approaches))

For each node in a tree, we can create node.merkle, a hash representing it's subtree.

This hash is formed by hashing the concatenation of the merkle of the left child, the node's value, and the merkle of the right child. Then, two trees are identical if and only if the merkle hash of their roots are equal (except when there is a hash collision.)

From there, finding the answer is straightforward: we simply check if any node in s has node.merkle == subroot.merkle

# Solution 2
from hashlib import sha256

def isSubtree(root: Optional[TreeNode], subroot: Optional[TreeNode]) -> bool:
    def hash_(x):
        S = sha256()
        S.update(x)
        return S.hexdigest()
        
    def merkle(node):
        if not node:
            return '#'
        m_left = merkle(node.left)
        m_right = merkle(node.right)
        node.merkle = hash_(m_left + str(node.val) + m_right)
        return node.merkle
        
    merkle(root)
    merkle(subroot)
    def dfs(node):
        if not node:
            return False
        return (node.merkle == subroot.merkle or 
                dfs(node.left) or dfs(node.right))
                    
    return dfs(root)