101. Symmetric Tree

melguachun

Melissa Guachun

Posted on January 24, 2022

101. Symmetric Tree

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.
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.

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

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

Given the starter code, we already have code for our edge cases:

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
Enter fullscreen mode Exit fullscreen mode
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
Enter fullscreen mode Exit fullscreen mode

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

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode
💖 💪 🙅 🚩
melguachun
Melissa Guachun

Posted on January 24, 2022

Join Our Newsletter. No Spam, Only the good stuff.

Sign up to receive the latest update from our blog.

Related

101. Symmetric Tree
beginners 101. Symmetric Tree

January 24, 2022