101. Symmetric Tree

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.

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

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

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.

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:

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

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:

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)

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.

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)

Comments

[Adriana DiPietro]

Great article!! If you add the language after the first three backticks (

```) when code highlighting, your code will be more readable.

For example, since you are coding in Python you would do (```

python) and then your code and finish off with the last three backticks. I hope this helps!!

[Melissa Guachun]

oooh thank you!!! I'll keep that in mind for future articles!!