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

Steps

1. Recursive Approach: We'll use a recursive function to traverse the root tree.
2. Same Structure and Values Check: For each node in root, we'll compare it with the subRoot. This comparison involves checking if the node values match and recursively checking if the left and right subtrees match. We use a helper function isSameTree for this.
3. Base Cases:
   • If subRoot is null, it means we've matched the structure, return true.
   • If root is null but subRoot is not, there's no match, return false.
   • If the node values don't match, return false.
4. Recursive Calls: Recursively compare the left and right subtrees of root and subRoot.

Explanation

The solution recursively checks if any subtree within root is identical to subRoot. The isSameTree function provides a clean way to compare the structure and values of two trees. The main function iterates through root to find a potential starting point for a matching subtree.

Code

using System;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public bool 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 bool 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(M + N) in the worst case due to the recursive call stack. The depth of the recursion can be at most the height of the larger tree.