using System;

using System.Collections.Generic;

​

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 static class Program

{

    public bool IsSubtree(TreeNode root, TreeNode subRoot) {

        // BFS the tree and match root and subRoot and do isSameTree

        Queue<TreeNode> queue = [];

        queue.Enqueue(root);

        while(queue.Count > 0)

        {

            var node = queue.Dequeue();

            if(node.val == subRoot.val && IsSameTree(node, subRoot)) return true;

            if(node.left is not null) queue.Enqueue(node.left);

            if(node.right is not null) queue.Enqueue(node.right);

        }

        return false;

    }

    public bool IsSameTree(TreeNode p, TreeNode q) {

        if(p is null && q is null) return true;

        if(p is not null && q is null) return false;

        if(p is null && q is not null) return false;

        if(p.val != q.val) return false;

​

        return p.val == q.val && IsSameTree(p.left, q.left) && IsSameTree(p.right, q.right);

    }

}