👨‍💻 738LeetCode

Is Subtree

Question

Given two trees A and B, check if B is a subtree of A. Empty tree is not a valid subtree.

Solution

Recursion.

class Solution:
    def is_subtree(self, root_a, root_b):
        def are_identical(root_a, root_b):
            if not root_b:
                return True
            if not root_a:
                return False
            if root_a.val == root_b.val:
                return are_identical(root_a.left, root_b.left) \
                       and are_identical(root_a.right, root_b.right)
            return False
    
    
        if not root_a or not root_b:
            return False
        if are_identical(root_a, root_b):
            return True
        return is_subtree(root_a.left, root_b) \
               or is_subtree(root_a.right, root_b)

Comment

Note it asks us to check if B is a subtree of A, and not the other way around.