101. Symmetric Tree
Tags: beginners, algorithms, python, codenewbie
Published: 2022-01-24 22:57:36


![Illustration from The Giving Tree by Shell Silverstein. Image is a boy hugging the tree. The tree is leaning forward, as if it were looking and embracing the boy.](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/3chsnmllh6jg71baaiy2.jpg)
This is the first binary tree problem in LeetCode! Since they're very common in technical assessments, I want to break this problem down as much as possible. 
The problem asks us, given the root of a binary tree,  check whether it is a mirror of itself (i.e, symmetrical).
Lets look at the first example: symmetrical means that if we start at the root of 1 and follow the dotted line, the binary tree is  split in half. The right side of the node should be a mirrored image of the left node and vice versa. 

![Binary tree that is symmetrical. ](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ah925xt84pq02xttc7yp.png)

To help us traverse the binary tree, let's label the left node as root A and the right node as root B. 

![Binary tree with two symmetrical branches. Root and branch A ! and branch B are identified](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ouht50cd034npbqdc0r4.png)

But before we start coding we have to solve for possible edge cases. Like what if the nodes don't match? Or if there aren't any nodes at all?

Let's think about it. If there are no nodes, meaning there is neither a branch A or a branch B, then we can return True because there are no nodes to compare. We can translate this into conditional logic, like 

```python3
if not a and not b: 
   return True
#if there are no nodes, none to compare return True
```
Now what if the nodes don't match? Let's use the same conditional knowledge.

```python3
if not a or not b: 
   return False
# if the nodes do not match return False
```
Given the starter code, we already have code for our edge cases:

```python3
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
```

```python3
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def same_tree(a,b):
            if not a and not b: 
                return True
            if not a or not b: 
                return False
```
Now we have code to handle edge cases if there are no nodes or if the nodes do not match. The next step is to determine if the values of branches are symmetrical. To help us achieve symmetry, I labeled the nodes as followed:

![Binary tree labeled as A and B. Children nodes labeled as A left, left, A left, right, B right, left, and B right, right](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/mgxvqgfozy5qc62emzvj.png)

From this diagram, we can see that root A left left is similar to root B right right and root A left right is equal to root B right left. 

```
root left left == root right right
root left right == root right left
```
We can use this logic to determine if the left and right nodes are similar. The conditional above will work for our best case that both branches are symmetrical, which we would then return True. 
In this step we have to do two things to check a branch's symmetry. We must check the value of branch A and branch B and check if `same_tree(a.left,b.right)` and `same_tree(a.right,b.left)`

```python3
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def same_tree(a,b):
            if not a and not b: 
                return True
            if not a or not b: 
                return False
            if a.val == b.val and same_tree(a.left,b.right) and same_tree(a.right,b.left): 
                return True
```
If the values of branch A and branch B are symmetrical, we will return it. Else we will return it as false.

```python3
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def same_tree(a,b):
            if not a and not b: 
                return True
            if not a or not b: 
                return False
            if a.val == b.val and same_tree(a.left,b.right) and same_tree(a.right,b.left):  #if values are the same, if conditional matches
                return True
            else:
                return False
        return same_tree(root.right,root.left)
```