0572.md

572. Subtree of Another Tree

Level:

Topic:

Question

Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise.

Input: root = [3,4,5,1,2], subRoot = [4,1,2]
Output: true\

Intuition

Recursive:

Check every node with subroot's root

• if there is a root and subtree equals subroot, return true
• otherwise, traverse to other nodes until all nodes are visited

Code

Time: O(n)
Space: O(n)

Recursive

public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null)
            return false;
        if (validate(root, subRoot))
            return true;
        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }

    private boolean validate(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null)
            return true;

        if (root1 == null || root2 == null)
            return false;

        if (root1.val != root2.val)
            return false;

        return validate(root1.left, root2.left) && validate(root1.right, root2.right);
    }