Symmetric Tree — LeetCode 101 Python Solution
EasyTreeDepth-First SearchBreadth-First SearchBinary Tree
- Problem
- #101
- Pattern
- Tree Traversal
- Reading time
- 3 min
- Source
- leetcode.com
The problem
Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).
Example
- Input
- root = [1,2,2,3,4,4,3]
- Output
- true
Python solution
Python
# 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 dfs(root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
if root1 == root2:
return True
if root1 is None or root2 is None or root1.val != root2.val:
return False
return dfs(root1.left, root2.right) and dfs(root1.right, root2.left)
return dfs(root.left, root.right)Complexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n) auxiliary |
Pattern: Tree Traversal
Choose the order — preorder, inorder, postorder, level — and the problem solves itself. LeetCode 101. Symmetric Tree is filed here because LeetCode tags it Tree and Binary Tree, which is the vocabulary this hub collects.
The tree traversal guide has the Python template for the pattern and the 225 LeetCode problems that use it.
Related problems
On a study list
This problem is on Top Interview 150.
Frequently asked questions
- How hard is LeetCode 101. Symmetric Tree?
- LeetCode 101. Symmetric Tree is rated Easy on LeetCode.
- What is the time complexity of LeetCode 101. Symmetric Tree?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 101. Symmetric Tree?
- The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 101. Symmetric Tree cover?
- LeetCode 101. Symmetric Tree is tagged Tree, Depth-First Search, Breadth-First Search and Binary Tree on LeetCode.