Start learning free

LESSON 324 OF 410 · BINARY TREES

Symmetric Tree in Python: Recursive Mirror Check with DFS

Practice O(n) Read the full explanation

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

 

Example 1:

Input: root = [1,2,2,3,4,4,3]
Output: True

Example 2:

Input: root = [1,2,2,None,3,None,3]
Output: False

 

Constraints:

  • The number of nodes in the tree is in the range [1, 1000].
  • Each node value is between -100 and 100.

 

Follow up: Could you solve it both recursively and iteratively?
STEP 1 OF 7
    Ctrl + Enter to check

    PYTHON · BINARY TREES

    Symmetric Tree in Python, explained

    Problem overview

    The method isSymmetric(self, root) receives the root of a binary tree and returns True if the tree is a mirror image of itself around its center, False otherwise. Each node has a val, a left child and a right child, and a missing child is None.

    The tree [1,2,2,3,4,4,3] is symmetric: below the root 1 there are two 2s, and the left 2 has children 3 and 4 while the right 2 has children 4 and 3, the same pair in reverse. The tree [1,2,2,null,3,null,3] is not symmetric. Both 2s have only a right child, a 3, and a mirror would need the left 2's child on the left of the right 2 and the other on the right.

    Approach: compare two subtrees at once

    Comparing a tree with its mirror image means checking that the left side is the reflection of the right side. A reflection swaps left and right at every level, so two nodes mirror each other when:

    • both are missing, or both exist and hold the same value, and
    • the left child of the first mirrors the right child of the second, and
    • the right child of the first mirrors the left child of the second.

    This is a recursive definition, so the code is a recursive helper, dfs(root1, root2), which answers "do these two subtrees mirror each other?". To test the whole tree, pass the root as both arguments: the helper then walks one copy leftwards while it walks the other copy rightwards, comparing a left-side node to its mirror position on the right.

    The alternative is an iterative version with a queue or a stack that holds pairs of nodes to compare. It follows the same pair rule, and the recursive form is shorter.

    Step by step

    1. Return self.dfs(root, root) from isSymmetric. A tree is symmetric when it mirrors itself.
    2. Declare dfs(self, root1, root2). The two parameters are nodes that should be mirror images of each other.
    3. Both empty: return True. not root1 and not root2 is true when both are None. Two empty subtrees mirror each other. This is also the base case that stops the recursion below the leaves.
    4. Exactly one empty: return False. The both-empty case has already returned, so not root1 or not root2 means exactly one node is missing, and the shapes differ.
    5. Different values: return False. Both nodes exist now, so reading val is safe.
    6. Check the outer pair. dfs(root1.left, root2.right) compares the left child of the first node with the right child of the second. If that fails, return False immediately.
    7. Return the inner pair. dfs(root1.right, root2.left) is all that remains, so its result is the answer.

    The solution in Python

    class Solution:
    def dfs(self, root1, root2): 
        if not root1 and not root2:
            return True
        if not root1 or not root2:
            return False
        if root1.val != root2.val:
            return False
        if not self.dfs(root1.left, root2.right):
            return False
        return self.dfs(root1.right, root2.left)
    def isSymmetric(self, root: TreeNode) -> bool:
        return self.dfs(root, root)

    Python details to notice:

    • not root1 is true when root1 is None. This works for tree nodes because an ordinary object is always truthy, unless its class defines __bool__ or __len__. A stricter, more explicit test is root1 is None.
    • The order of the three checks matters. Reading root1.val on a None would raise AttributeError: 'NoneType' object has no attribute 'val', and the two earlier checks make sure that never happens.
    • dfs is a method, so it is called as self.dfs(...), and it needs self as its first parameter.
    • The method returns the result of the last call directly, instead of writing if ...: return True else: return False.

    Complexity

    • Time: O(n), where n is the number of nodes. Because the root is passed as both arguments, each node is visited twice (once from each side), which is still linear. The function returns early at the first mismatch.
    • Space: O(h) for the recursion stack, where h is the height of the tree: about log n for a balanced tree and up to n for a tree shaped like a list. Python's default recursion limit is 1000 nested calls. A symmetric tree with up to 1000 nodes is at most about 500 levels deep, and a lopsided tree fails the mirror test within a few calls, so the limit is not a concern for this problem.

    Edge cases and common mistakes

    • A single node. [1] is symmetric: dfs compares the node to itself, the values match, and both children pairs are None.
    • Same values, different shape. [1,2,2,3,None,None,3] is symmetric, while [1,2,3] is not, because 2 and 3 differ. Shape and values must both match.
    • Comparing the wrong children. dfs(root1.left, root2.left) would test whether a tree equals itself, not whether it mirrors itself. The crossing, left with right, is the whole idea.
    • Checking only the root's two children. Equal values at one level do not imply symmetry deeper down.

    Testing

    With trees written in level order, [1,2,2,3,4,4,3] gives True, [1,2,2,None,3,None,3] gives False, [1] gives True and [1,2,3] gives False.

    Keep going with PythonAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free