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 itsel…

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

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:

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

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)

Print Share Comment Cite Upload Translate
APA
Melissa Guachun | Sciencx (2024-03-29T11:41:36+00:00) » 101. Symmetric Tree. Retrieved from https://www.scien.cx/2022/01/24/101-symmetric-tree/.
MLA
" » 101. Symmetric Tree." Melissa Guachun | Sciencx - Monday January 24, 2022, https://www.scien.cx/2022/01/24/101-symmetric-tree/
HARVARD
Melissa Guachun | Sciencx Monday January 24, 2022 » 101. Symmetric Tree., viewed 2024-03-29T11:41:36+00:00,<https://www.scien.cx/2022/01/24/101-symmetric-tree/>
VANCOUVER
Melissa Guachun | Sciencx - » 101. Symmetric Tree. [Internet]. [Accessed 2024-03-29T11:41:36+00:00]. Available from: https://www.scien.cx/2022/01/24/101-symmetric-tree/
CHICAGO
" » 101. Symmetric Tree." Melissa Guachun | Sciencx - Accessed 2024-03-29T11:41:36+00:00. https://www.scien.cx/2022/01/24/101-symmetric-tree/
IEEE
" » 101. Symmetric Tree." Melissa Guachun | Sciencx [Online]. Available: https://www.scien.cx/2022/01/24/101-symmetric-tree/. [Accessed: 2024-03-29T11:41:36+00:00]
rf:citation
» 101. Symmetric Tree | Melissa Guachun | Sciencx | https://www.scien.cx/2022/01/24/101-symmetric-tree/ | 2024-03-29T11:41:36+00:00
https://github.com/addpipe/simple-recorderjs-demo