LeetCode 101: Symmetric Tree Solution in Python Explained

Problem Statement

In LeetCode 101, you’re given the root of a binary tree. Your task is to return true if the tree is symmetric—its left and right subtrees are mirror images in structure and value—or false if they’re not. This builds on tree comparison from LeetCode 100: Same Tree, shifting focus to symmetry rather than exact equality.

Constraints

• Number of nodes: 0 <= n <= 1000
• Node values: -100 <= Node.val <= 100

Example

Let’s see some cases:

Copy codeInput: root = [1,2,2,3,4,4,3]
      1
     / \
    2   2
   / \ / \
  3  4 4  3
Output: true
Explanation: Left (2,3,4) mirrors Right (2,4,3).

Copy codeInput: root = [1,2,2,null,3,null,3]
      1
     / \
    2   2
     \   \
     3    3
Output: false
Explanation: Left (2,null,3) doesn’t mirror Right (2,null,3).

Copy codeInput: root = []
Output: true
Explanation: Empty tree is symmetric.

These examples show we’re checking for mirror symmetry.

Understanding the Problem

How do you solve LeetCode 101: Symmetric Tree in Python? Take root = [1,2,2,3,4,4,3]. We need to confirm it’s symmetric—left subtree (2,3,4) mirrors right subtree (2,4,3), true. For [1,2,2,null,3,null,3], left and right differ structurally, false. This isn’t a BST recovery like LeetCode 99: Recover Binary Search Tree; it’s about symmetry validation. We’ll use: 1. Recursive Mirroring: O(n) time, O(h) space—our best solution. 2. Stack-Based Mirroring: O(n) time, O(h) space—an alternative.

Let’s dive into the primary solution.

Solution 1: Recursive Mirroring Approach (Primary)

Explanation

Recursive Mirroring checks symmetry by recursively comparing the left and right subtrees as mirror images—left’s left with right’s right, left’s right with right’s left. If both are null, they’re symmetric; if values or structures differ, they’re not. It’s the best solution due to its clarity, efficiency, and natural fit for tree symmetry.

For [1,2,2,3,4,4,3]:

• Root: 1 (symmetric root).
• Left (2,3,4) vs. Right (2,4,3):
• Values: 2 = 2.
• Left.left (3) = Right.right (3).
• Left.right (4) = Right.left (4).
• True.

Step-by-Step Example

Assume a TreeNode class: class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val; self.left = left; self.right = right.

Example 1: root = [1,2,2,3,4,4,3]

Goal: Return true.

• Start: Call isSymmetric(root=1) → isMirror(1.left=2, 1.right=2).
• Step 1: left = 2, right = 2.
• Not null, 2 = 2, true.
• Outer: isMirror(left.left=3, right.right=3).
• 3 = 3, no children, true.
• Inner: isMirror(left.right=4, right.left=4).
• 4 = 4, no children, true.
• Finish: Return true.

Example 2: root = [1,2,2,null,3,null,3]

Goal: Return false.

• Start: isMirror(2, 2).
• Step 1: left = 2, right = 2.
• 2 = 2, true.
• Outer: isMirror(left.left=None, right.right=3).
• None ≠ 3, false, stop.
• Finish: Return false.

Example 3: root = []

Goal: Return true.

• Start: root = None.
• Step 1: Null root, true.
• Finish: Return true.

How the Code Works (Recursive Mirroring) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codeclass TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def isSymmetric(root: TreeNode) -> bool:
    # Line 1: Define helper function to compare subtrees
    def isMirror(left: TreeNode, right: TreeNode) -> bool:
        # left = left subtree, right = right subtree (e.g., left=2, right=2)

        # Line 2: Check if both nodes are null
        if not left and not right:
            # If both are None (e.g., children of leaf nodes), symmetric
            return True

        # Line 3: Check if one node is null
        if not left or not right:
            # If one is None and other isn’t (e.g., None vs. 3), not symmetric
            return False

        # Line 4: Compare current node values
        if left.val != right.val:
            # If values differ (e.g., 2 ≠ 3), not symmetric
            return False

        # Line 5: Check outer symmetry (left.left vs. right.right)
        outer = isMirror(left.left, right.right)
        # Recursively compares outer children (e.g., 3 vs. 3)
        # Ensures left’s left mirrors right’s right

        # Line 6: Check inner symmetry (left.right vs. right.left)
        inner = isMirror(left.right, right.left)
        # Recursively compares inner children (e.g., 4 vs. 4)
        # Ensures left’s right mirrors right’s left

        # Line 7: Return combined result
        return outer and inner
        # True if both outer and inner pairs are symmetric (e.g., true for [2,3,4] vs. [2,4,3])

    # Line 8: Handle null root
    if not root:
        # If root is None, tree is symmetric (empty mirror)
        return True

    # Line 9: Start mirroring from root’s children
    return isMirror(root.left, root.right)
    # Compares left and right subtrees (e.g., 2 vs. 2)
    # Returns final symmetry result

This detailed breakdown clarifies how recursive mirroring validates tree symmetry efficiently.

Alternative: Stack-Based Mirroring Approach

Explanation

Stack-Based Mirroring uses a stack to compare nodes iteratively, pushing pairs of left and right children in mirrored order (left.left with right.right, left.right with right.left). Pop and check values and structure. It’s a practical alternative, avoiding recursion while maintaining symmetry checks.

For [1,2,2,3,4,4,3]:

• Stack: [(2,2)], pop, match, push (3,3), (4,4).
• All match, true.

Step-by-Step Example (Alternative)

For [1,2,2,3,4,4,3]:

• Start: stack = [(2,2)].
• Step 1: Pop (2,2), 2 = 2, push (3,3), (4,4).
• Step 2: Pop (4,4), 4 = 4, no children.
• Step 3: Pop (3,3), 3 = 3, no children.
• Finish: Return true.

For [1,2,2,null,3,null,3]:

• Step 1: Pop (2,2), push (None,3), (3,None).
• Step 2: Pop (3,None), mismatch, false.
• Finish: Return false.

How the Code Works (Stack-Based)

Copy codedef isSymmetricStack(root: TreeNode) -> bool:
    if not root:
        return True
    stack = [(root.left, root.right)]
    while stack:
        left, right = stack.pop()
        if not left and not right:
            continue
        if not left or not right or left.val != right.val:
            return False
        stack.append((left.left, right.right))
        stack.append((left.right, right.left))
    return True

Complexity

• Recursive Mirroring:
• Time: O(n) – visits each node once.
• Space: O(h) – recursion stack, h = height.
• Stack-Based Mirroring:
• Time: O(n) – visits each node once.
• Space: O(w) – stack size, w = max width.

Efficiency Notes

Recursive Mirroring is the best solution with O(n) time and O(h) space, offering a clean, intuitive approach—Stack-Based Mirroring matches time complexity with O(w) space, providing a robust alternative when recursion is avoided.

Key Insights

• Mirroring: Left.left = Right.right, Left.right = Right.left.
• Symmetry: Structure and value match.
• Traversal: Full tree comparison.

Additional Example

For root = [1,2,2,3,3]:

• Goal: false.
• Recursive: Left (2,3) ≠ Right (2,3) structurally → false.

Edge Cases

• Empty Tree: [] → true.
• Single Node: [1] → true.
• Asymmetric Values: [1,2,2,3,4] → false.

Both solutions handle these well.

Final Thoughts

LeetCode 101: Symmetric Tree in Python is a delightful symmetry challenge. The Recursive Mirroring solution stands out for its efficiency and clarity, while Stack-Based Mirroring offers a non-recursive option. Want more? Try LeetCode 100: Same Tree for exact comparison or LeetCode 94: Binary Tree Inorder Traversal for traversal basics. Ready to practice? Solve LeetCode 101 on LeetCode with [1,2,2,3,4,4,3], aiming for true—test your skills now!