Domain 1EasyCORE

Symmetric Tree

The problem asks us to determine whether a binary tree is symmetric around its center. In other words, we need to check if the left subtree is a mirror reflection of the right subtree.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Tree#Depth-first Search#Breadth-first Search

101. Symmetric Tree

Model: qwen2.5-coder:14b
Topics: Tree,Depth-first Search,Breadth-first Search
FAANG asked: 1
Acceptance rate: 48.4%


Problem Breakdown

The problem asks us to determine whether a binary tree is symmetric around its center. In other words, we need to check if the left subtree is a mirror reflection of the right subtree.

Inputs:

  • root: The root node of a binary tree.

Outputs:

  • A boolean value indicating whether the tree is symmetric.

Implicit Constraints or Tricky Edge Cases:

  • An empty tree (single node) should be considered symmetric.
  • Trees with only one child on either side are not symmetric unless both sides are identical.
  • The values in the nodes can range from -100 to 100, so we need to handle negative numbers.

Intuition

A brute-force approach would involve checking each pair of corresponding nodes manually, which could be inefficient and error-prone. Instead, we can leverage recursion or iteration to compare subtrees more systematically.

The key insight is that two trees are mirrors of each other if:

  1. Their root values are the same.
  2. The left subtree of one tree is a mirror of the right subtree of the other tree.
  3. The right subtree of one tree is a mirror of the left subtree of the other tree.

This recursive approach allows us to break down the problem into smaller subproblems, making it easier to solve.

Approach

We will use a recursive function to check if two subtrees are mirrors of each other. The base case will handle empty trees and mismatched values. For non-empty trees, we will recursively compare the left subtree of one tree with the right subtree of the other and vice versa.

Algorithm Steps:

  1. Define a helper function isMirror that takes two nodes as arguments.
  2. In the isMirror function:
    • If both nodes are null, return true (base case).
    • If only one node is null or their values differ, return false.
    • Recursively check if the left subtree of the first node is a mirror of the right subtree of the second node and vice versa.
  3. Call the isMirror function with the left and right children of the root.

Complexity Analysis

  • Time Complexity: O(n), where n is the number of nodes in the tree. Each node is visited once.
  • Space Complexity: O(h), where h is the height of the tree. This accounts for the recursion stack. In the worst case, the space complexity is O(n) for a skewed tree.

Solution

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

def isSymmetric(root: TreeNode) -> bool:
    def isMirror(left: TreeNode, right: TreeNode) -> bool:
        if not left and not right:
            return True
        if not left or not right:
            return False
        return (left.val == right.val) and isMirror(left.left, right.right) and isMirror(left.right, right.left)
    
    return isMirror(root.left, root.right)

Edge Cases Handled

  • Empty Tree: The function correctly returns true for an empty tree.
  • Single Node Tree: A single node tree is symmetric by definition.
  • Trees with Different Structures: Trees where one side has more nodes than the other are handled by checking null values.
  • Negative Values in Nodes: The comparison of node values works correctly with negative numbers.