/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSubtree(TreeNode s, TreeNode t) {
     // return dfs(s, t); // 8 ms
     // return bfs(s,t); // 7 ms
      return traverse(s,t); // 6ms;
    }
    private boolean isIdentical(TreeNode s, TreeNode t){
    if(s == null && t == null) return true;
    if(s == null || t == null) return false;

    if(t.val != s.val) return false;
    return isIdentical(s.right, t.right) && isIdentical(s.left, t.left);
  }

   private boolean traverse(TreeNode s, TreeNode t) {
     return s != null && (isIdentical(s, t) || traverse(s.left, t) || traverse(s.right, t));
   }

  private boolean bfs(TreeNode s, TreeNode t) {
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(s);
    while (!queue.isEmpty()) {
        TreeNode current = queue.poll();
        if (current.val == t.val && isIdentical(current, t)) return true;
        if (current.left != null) queue.offer(current.left);
        if (current.right != null) queue.offer(current.right);
    }
    return false;
  }
  private boolean dfs(TreeNode s, TreeNode t) {
    Stack<TreeNode> stack = new Stack<>();
      stack.push(s);
      while(!stack.empty()){
        TreeNode current = stack.pop();
        if(current.val == t.val && isIdentical(current, t)){
          return true;
        }
        if(current.right != null) stack.push(current.right);
        if(current.left != null) stack.push(current.left);
      }
      return false;
  }
}