[isMirror] DFS (Recursion, One/Two Stacks) + BFS (Queue) Solution in Java
Reference: LeetCode EPI 9.2\nDifficulty: Easy\n\n## Problem\n\n> Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).\
Reference: [LeetCode](https://leetcode.com/problems/symmetric-tree/) <span class="gray">EPI 9.2</span>\nDifficulty: <span class="green">Easy</span>\n\n## Problem\n\n> Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).\n\n**Example:** \n\n`[1,2,2,3,4,4,3]` is symmetric:\n\n```java\n    1\n   / \\\n  2   2\n / \\ / \\\n3  4 4  3\n```\n\nBut the following `[1,2,2,null,3,null,3]` is not:\n\n```java\n    1\n   / \\\n  2   2\n   \\   \\\n   3    3\n```\n\n**Follow up:** Bonus points if you could solve it both `recursively` and `iteratively`.\n\n\n\n\n## Analysis\n\n**Idea:** A tree is symmetric if it is a `mirror reflection` of itself.\n\n**Note:** Distinguish the concept of `symmetric` (one tree) and `mirror reflection` (two trees).\n\n```java\n    1\n   / \\\n  2   2       t1 & t2\n / \\ / \\\n3  4 4  3\n|  | |  |\n---|-|----->  isMirror(t1.left, t2.right)\n   | |      \n   -------->  isMirror(t1.right, t2.left)\n```\n\nThe question is when are two trees a mirror reflection of each other? **Three conditions:**\n\n- Their two roots have the same value.\n- The right subtree `t1.right` of each tree `t1` is a mirror reflection of the left subtree `t2.left` of the other tree `t2`.\n- The left subtree `t1.left` of each tree `t1` is a mirror reflection of the right subtree `t2.right` of the other tree `t2`.\n\n**Bad Idea (the wrong direction):**\n\nA tree is symmetric if its left subtree is symmetric and its right subtree is symmetric. Consider this case:\n\n```java\n    1\n   / \\\n  2   2\n / \\ / \\\n3  4 4  3\n```\n\nTwo subtrees of root are not symmetric, but the root is symmetric.\n\n\nFrom EPI, swapping any subtrees of a tree and comparing with the original is also workable.\n\n\n\n### Recursion\n\nCome up with the recursive structure.\n\n```java\npublic boolean isSymmetric(TreeNode root) {\n  return isMirror(root, root);\n}\n\nprivate boolean isMirror(TreeNode t1, TreeNode t2) {\n  // base case\n  if (t1 == null && t2 == null) return true;\n  if (t1 == null || t2 == null) return false;\n  // check values\n  if (t1.val != t2.val) return false;\n  // check left subtree and right subtree\n  return isMirror(t1.right, t2.left) && isMirror(t1.left, t2.right);\n}\n```\n\n**Improvement:**\n\nActually, there is not too much improvement since it is bounded by a constant `2`.\n\n```java\npublic boolean isSymmetric(TreeNode root) {\n  if (root == null) { // required\n    return true;\n  }\n  return isMirror(root.left, root.right); // so t1 and t2 are different trees\n}\n```\n\n**Time:** `O(N)` because we traverse the entire input tree once (`\\sim 2N`).\n**Space:** `O(h)`\n\n\n\n\n### Iteration (One/Two Stacks)\n\nUse two stacks to simulate the recursive method.\n\n**Note:** Null check => Value check\n\n```java\npublic boolean isSymmetric(TreeNode root) {\n  if (root == null) { // need checking because we use root\'s value\n    return true;\n  }\n  Stack<TreeNode> lStack = new Stack<>();\n  Stack<TreeNode> rStack = new Stack<>();\n  // Preorder-like traversal\n  lStack.push(root.left); rStack.push(root.right);\n  \n  while (lStack.size() > 0 && rStack.size() > 0)  {\n    TreeNode t1 = lStack.pop();\n    TreeNode t2 = rStack.pop();\n    // null check\n    if (t1 == null && t2 == null) continue;\n    if (t1 == null || t2 == null) return false;\n    // value check\n    if (t1.val != t2.val) return false;\n    // push children\n    lStack.push(t1.right); lStack.push(t1.left); // could be null\n    rStack.push(t2.left);  rStack.push(t2.right);\n  }\n  // One of the stack might be empty\n  return lStack.size() == 0 && rStack.size() == 0;\n}\n```\n\nOr just use one stack:\n\n- Be careful of the ordering of pushing.\n\n```java\npublic boolean isSymmetric(TreeNode root) {\n  if (root == null) {\n    return true;\n  }\n  if (root.left == null && root.right == null) return true;\n  if (root.left == null || root.right == null) return false;\n  // children are not null\n  Stack<TreeNode> stack = new Stack<>();\n  stack.push(root.left);\n  stack.push(root.right);\n  \n  while (stack.size() > 0) {\n    TreeNode t1 = stack.pop();\n    TreeNode t2 = stack.pop();\n    // null check\n    if (t1 == null && t2 == null) continue;\n    if (t1 == null || t2 == null) return false;\n    // value check\n    if (t1.val != t2.val) return false;\n    // push children\n    stack.push(t1.right); stack.push(t2.left); // could be null\n    stack.push(t1.left); stack.push(t2.right);\n  }\n  \n  return true;\n}\n```\n\n\n**Time:** `O(N)`\n**Space:** `O(h)`\n\n\n\n\n### Iteration (BFS)\n\nCompare nodes at each layer.\n- Each two consecutive nodes in the queue should be equal.\n- Each time, two nodes are extracted and their values are compared.\n- Then their right and left children of the two nodes are enqueued in opposite order.\n\n```java\n    1\n   / \\\n  2   2     queue: 2    2 (t1)\n / \\ / \\\n3  4 4  3   queue: 4    4    3    3\n                           t2.r t1.l\n```\n\n```java\npublic boolean isSymmetric(TreeNode root) {\n  if (root == null) {\n    return true;\n  }\n  Queue<TreeNode> queue = new LinkedList<>();\n  queue.offer(root.left);\n  queue.offer(root.right);\n\n  while (queue.size() > 0) {\n    TreeNode t1 = queue.poll();\n    TreeNode t2 = queue.poll();\n    // check\n    if (t1 == null && t2 == null) continue;\n    if (t1 == null || t2 == null) return false;\n    if (t1.val != t2.val) return false;\n    // offer children\n    queue.offer(t1.left);\n    queue.offer(t2.right);\n\n    queue.offer(t1.right);\n    queue.offer(t2.left);\n  }\n  return true;\n}\n```\n\n\n**Time:** `O(N)`\n**Space:** `O(w)` where `w` is the maximum number nodes in a level of the tree.\n\n
['Breadth-First Search', 'Recursion', 'Iterator', 'Java']