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 with the same structure and node values with subRoot and false otherwise.

A subtree of a binary tree root is a tree that consists of a node in root and all of this node's descendants. The tree root may contain multiple subtrees of the same structure and node values with subRoot.

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,6], subRoot = [4,1,2] Output: false

Steps

1. Recursive Approach: We'll use a recursive approach to traverse both trees simultaneously.
2. isSameTree Function: Create a helper function isSameTree that checks if two trees are structurally identical. This will be used recursively to compare subtrees.
3. isSubtree Function: The main isSubtree function will recursively traverse root. At each node, it checks if the subtree rooted at that node is identical to subRoot using isSameTree. If a match is found, it returns true. Otherwise, it continues the traversal.
4. Base Cases:
   • If root is null, return false (no subtree can be found).
   • If subRoot is null, return true (empty subRoot is always a subtree).
   • If root and subRoot are not structurally identical, continue the traversal.
5. Recursive Calls: Recursively call isSubtree on the left and right subtrees of root.
6. Return Value: The function returns true if a match is found, and false otherwise.

Explanation

The isSameTree function performs a simple depth-first traversal comparing nodes at each level. The isSubtree function cleverly uses this to check if any subtree within the larger tree matches the structure of the smaller tree. By recursively checking at every node in the larger tree, it efficiently explores all possible subtrees.

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) return false;
        if (isSameTree(root, subRoot)) return true;
        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }

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

Complexity

• Time Complexity: O(M * N), where M is the number of nodes in root and N is the number of nodes in subRoot. In the worst case, we might compare subRoot with every node in root.
• Space Complexity: O(max(M, N)) in the worst case due to the recursive calls' stack depth, which can be proportional to the height of the larger tree. If the trees are highly unbalanced, the depth could be as high as the number of nodes in the largest tree.