Subtree of Another Tree easy

Problem Statement

Given the roots of two binary trees root and subRoot, return true if there is a subtree of root which is equivalent to subRoot, otherwise return false.

A subtree of a binary tree root is a tree that consists of a node in root and its descendants.

Example 1

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

Example 2

Input: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2] Output: false

Steps

1. Tree Traversal: We need a way to traverse both trees systematically. Depth-First Search (DFS) is a good choice.
2. Subtree Check: Create a function that checks if two trees are identical. This function will compare the nodes recursively.
3. Main Logic: Traverse the main tree (root). At each node, compare the subtree rooted at that node with subRoot. If a match is found, return true.

Explanation

The solution uses a recursive approach. The core idea is to check if the subtree rooted at each node in the main tree matches the subRoot tree. The isSameTree function compares two trees for structural and value equality. The isSubtree function performs a DFS traversal of the main tree, invoking isSameTree at each node to check for a match.

Code

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = val === undefined ? 0 : val;
        this.left = left === undefined ? null : left;
        this.right = right === undefined ? null : right;
    }
}

function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
    if (p === null && q === null) return true;
    if (p === null || q === null) return false;
    return (
        p.val === q.val &&
        isSameTree(p.left, q.left) &&
        isSameTree(p.right, q.right)
    );
}

function isSubtree(root: TreeNode | null, subRoot: TreeNode | null): boolean {
    if (subRoot === null) return true; //Empty subRoot is always a subtree
    if (root === null) return false;

    if (isSameTree(root, subRoot)) {
        return true;
    }

    return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}


//Example Usage
const root = new TreeNode(3, new TreeNode(4, new TreeNode(1), new TreeNode(2)), new TreeNode(5));
const subRoot = new TreeNode(4, new TreeNode(1), new TreeNode(2));
console.log(isSubtree(root, subRoot)); // Output: true

const root2 = new TreeNode(3, new TreeNode(4, new TreeNode(1), new TreeNode(2)), new TreeNode(5));
const subRoot2 = new TreeNode(4, new TreeNode(1), new TreeNode(2, new TreeNode(0)));
console.log(isSubtree(root2, subRoot2)); // Output: false

Complexity

• Time Complexity: O(M * N), where N is the number of nodes in root and M is the number of nodes in subRoot. In the worst case, isSameTree might be called for every node in root.
• Space Complexity: O(max(N, M)) in the worst case due to the recursive call stack depth. The space used is proportional to the height of the taller tree.