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)