JavaScript recursive and iterative solutions
The idea is to check whether the tree's left and right subtrees are mirroring each other, we can use preorder traversal:\n\nvar isSymmetric = function(root) {\n
The idea is to check whether the tree's left and right subtrees are mirroring each other, we can use preorder traversal:\n```\nvar isSymmetric = function(root) {\n    if (!root) { // Sanity check\n        return true;\n    }\n\n    // Check if tree s & t are mirroring each other\n    function isMirror(s, t) {\n        if (!s && !t) {\n            return true; // Both nodes are null, ok\n        }\n        if (!s || !t || s.val !== t.val) {\n            return false; // Found a mismatch\n        }\n        // Compare the left subtree of `s` with the right subtree of `t`\n        // and the right subtree of `s` with the left subtree of `t`\n        return isMirror(s.left, t.right) && isMirror(s.right, t.left);\n    }\n\n    return isMirror(root.left, root.right);\n};\n```\nAs it's preorder DFS, time complexity is `O(n)`, and space complexity is `O(1)` if we ignore the recursion stack which is the height of the tree.\n\nThe question asks us to implement the solution iteratively, and it's easy to convert the above preorder to make it traverse iteratively using stack:\n```\nfunction isMirror(p, q) {\n    // Create two stacks\n    var s1 = [p], s2 = [q];\n\n    // Perform preorder traversal\n    while (s1.length > 0 || s2.length > 0) {\n        var n1 = s1.pop(), n2 = s2.pop();\n\n        // Two null nodes, let's continue\n        if (!n1 && !n2) continue;\n\n        // Return false as long as there is a mismatch\n        if (!n1 || !n2 || n1.val !== n2.val) return false;\n\n        // Scan tree s from left to right\n        // and scan tree t from right to left\n        s1.push(n1.left); s1.push(n1.right);\n        s2.push(n2.right); s2.push(n2.left);\n    }\n\n    return true;\n}\n```\nTime complexity is still `O(n)`, and space complexity is the height of the tree.\n\nAnother solution is to use BFS, we just need to traverse both subtrees in level order, one from left to right, and the other is right to left, let's modify the above `isMirror` function to the following:\n```\nfunction isMirror(s, t) {\n    var q1 = [s], q2 = [t];\n\n    // Perform breadth-first search\n    while (q1.length > 0 || q2.length > 0) {\n        // Dequeue\n        var n1 = q1.shift(), n2 = q2.shift();\n\n        // Two null nodes, let's continue\n        if (!n1 && !n2) continue;\n\n        // Return false as long as there is a mismatch\n        if (!n1 || !n2 || n1.val !== n2.val) return false;\n\n        // Scan tree s from left to right\n        // and scan tree t from right to left\n        q1.push(n1.left); q1.push(n1.right);\n        q2.push(n2.right); q2.push(n2.left);\n    }\n\n    return true;\n}\n```\nTime complexity is `O(n)` and space complexity is the width of the tree.
[]