101. Symmetric Tree 🚀

Solution Developed In:

Explaining The Question

So, we're given a Binary Tree and we have to check if it's a symmetric tree. Meaning that from the tree, it should be that of a mirror. We don't need to check the given root node, because that won't ever have a mirror. But it's left and right children need to be mirrored.

Mirrored meaning, that on the left side of the tree, the right side of the tree should have the same values but with their children swapped. It sounds confusing and it is a little. Visually speaking it's easy to imagine but to get this down into code, it's a little more complicated.

---

Recommended Knowledge

1. Binary Trees
2. Binary Tree Traversals
3. Post Order Traversal
4. Javascript Call Stack

What do we know?

1. We have a Binary Tree and we need to check if it's a symmetric tree. Meaning that from the tree should be that of a mirror. We don't need to check the given root node, because that won't ever have a mirror. But it's left and right children need to be mirrored.
2. We know that at any given node, it's children should have the same value but with their children swapped. Meaning that on one side, it's on the left and on the other side it's on the right.

How we're going to do it:

We're going to perform post-order traversal on both sides of the tree at the same time. Meaning, that on the left side, we're going to go as far left as possible, and on the right side, we're going to go as far right as possible. Compare the values of the nodes on both sides. If they're the same, then we're good. If not, we know it's a bad tree.

We're going to do this recursively.

1. Firstly, we need to treat every node as if they're all the same. Meaning we subject every node to the same process. So firstly we ask the nodes from both the left and right trees if they're empty? If this is the case, it mean's we reached the end of the binary tree without error. Meaning it's a symmetric tree.
2. We then ask 'Are the left and right trees both not empty?'. Meaning that one of them isn't a leaf node while the other is. If this is the case, then we know it's a bad tree. So we return false
3. We then compare values of both trees. 'Is the current left value the same as the current right value?' If this is the case, we have symmetrically nodes. If not, we return false
4. We then continue our search of the right and lefts trees until we have exhausted the tree. Meaning we have visited every node we can.
5. Once all nodes are visited, we ask if the trees was symmetric. Meaning that we have visited every node and we have checked if they're symmetric. If they were, then we return true. If not, we return false. If we got a false anywhere, it would have bubbled up through the stack to let us know that we had a bad node and thus this is a bad tree. If they were all true, then we return true.

Big O Notation:

• Time Complexity: O(n) | Where n is the number of nodes the tree has | As we will always be traversing the entire tree
• Space Complexity: O(h) | As we will be using the call Stack to store the nodes | Although, it can be argued that the Space Complexity is **O(n)** as in the worst case, the call stack contains as many nodes n as the tree has.

' Could this be improved? ' Yes! Morris Traversal could do this problem in O(1) space complexity. But Morris Traversal is tricky and tough to read. For the sake of simplicity, I don't use it here.

Leetcode Results:

See Submission Link:

• Runtime: 63 ms faster than 96.46% of JavaScript online submissions for Symmetric Tree
• Memory Usage: 55.6 MB, less than 44.80% of JavaScript online submissions for Symmetric Tree

---

The Solution

var isSymmetric = function (left_tree, right_tree = left_tree) {

    /* -------------------------------------------------------------------------- */
    /*                             101. Symmetric Tree                            */
    /* -------------------------------------------------------------------------- */

    /**
     * @author  Samuel Hinchliffe
     * @see    {@link linkedin.com/in/samuel-hinchliffe-🚀-2bb5801a5/ | Author's Linkedin }
     * @see    {@link github.com/Samuel-Hinchliffe}
    */

     // https://leetcode.com/submissions/detail/684314946/

    // Both are trees are the same
    if (!left_tree && !right_tree) {
        return true;
    }

    // One exists without another?
    if (!left_tree || !right_tree) {
        return false;
    }

    // Are left and right of same value?
    // If not return false
    if (left_tree.val != right_tree.val) {
        return false;
    }

    // Do all the left trees and right trees
    let outer_tree = isSymmetric(left_tree.left,  right_tree.right);
    let inner_tree = isSymmetric(left_tree.right, right_tree.left);

    // Are both trees the same?
    return outer_tree && inner_tree;
};