101. Symmetric Tree 🚀
Tags: javascript, tutorial, leetcode, programming
Published: 2022-05-16 19:05:54


### Solution Developed In:
![JavaScript](https://img.shields.io/badge/javascript-%23323330.svg?style=for-the-badge&logo=javascript&logoColor=%23F7DF1E)

![image](https://assets.leetcode.com/users/images/56a48553-cb14-4012-adb9-25f642e92398_1650484499.6721277.gif)

## 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](https://www.geeksforgeeks.org/binary-tree-set-1-introduction/)
2. [Binary Tree Traversals](https://www.geeksforgeeks.org/binary-tree-traversals/)
3. [Post Order Traversal](https://www.geeksforgeeks.org/post-order-traversal/)
4. [Javascript Call Stack](https://www.geeksforgeeks.org/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](https://en.wikipedia.org/wiki/Tree_traversal#Morris_traversal) could do this problem in ***O(1) space complexity***. But [Morris Traversal](https://en.wikipedia.org/wiki/Tree_traversal#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

[![LeetCode](https://img.shields.io/badge/LeetCode-000000?style=for-the-badge&logo=LeetCode&logoColor=#d16c06)](https://leetcode.com/submissions/detail/684314946/)


***

# 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;
};


```