Subtree of another tree - rFronteddu/general_wiki GitHub Wiki

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.

A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node's descendants. The tree tree could also be considered as a subtree of itself.

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) {
            // If root is null, subRoot must also be null to be a subtree
            return subRoot == null; 
        }
        // Check if the current tree is identical to subRoot
        if (isSameTree(root, subRoot)) {
            return true;
        }
        // Recursively check the left and right subtrees
        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }

    private boolean isSameTree(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) {
            // Both trees are empty
            return true; 
        }
        if (t1 == null || t2 == null) {
            // One tree is empty and the other is not
            return false; 
        }
        if (t1.val != t2.val) {
            // The values of the nodes do not match
            return false; 
        }
        // Recursively check the left and right subtrees
        return isSameTree(t1.left, t2.left) && isSameTree(t1.right, t2.right);
    }
}