Symmetric Tree

TARGET DECK: Leetcode FILE TAGS: Easy

---

Intuition

• Traverse left and right at the same time.
• Notice that in order for a tree to be symmetric, it must hold the property that the left node of the root must equal the right node of the root.
• This property holds for all cases.
• Have to be careful about None, in which you handle this by checking if both are None, then return true, and otherwise if one or the other is none, return false.

Complexity

Runtime

$O(N)$

Space

$O(N)$ given a linear height tree.

Code

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def r(leftHalfNode, rightHalfNode):
            if leftHalfNode == rightHalfNode == None:
                return True
            if leftHalfNode == None or rightHalfNode == None:
                return False
            if leftHalfNode.val != rightHalfNode.val:
                return False
            if r(leftHalfNode.left, rightHalfNode.right) is False:
                return False
            if r(leftHalfNode.right, rightHalfNode.left) is False:
                return False
            return True
 
        return r(root.left, root.right)

Notes

Cards

START Basic Front: Symmetric Tree Back: Traverse both sides of the tree at once. The left node of the root must equal the right node of the root.

END

---

References

• Symmetric Tree