Symmetrical Tree

Tags

Symmetrical Tree

Category

Binary Trees

Difficulty

Medium

Problem Statement

Given a binary tree, determine whether it is a mirror of itself, i.e., symmetric around its center. A tree is symmetric if the left subtree is a mirror reflection of the right subtree.

Intuition

A tree is symmetric if for every pair of corresponding nodes on opposite sides, the values are equal and their subtrees mirror each other. Specifically, the left child of the left subtree must match the right child of the right subtree, and vice versa. We can check this by traversing both halves simultaneously in a mirrored fashion.

Approach

  1. If the tree is empty, return true (an empty tree is symmetric).
  2. Define a helper function that takes two nodes to compare.
  3. Base cases: a. Both nodes are null: return true (symmetric at this position). b. One is null and the other is not: return false (asymmetric). c. Values differ: return false.
  4. Recursive step: return true only if: a. The left child of node1 is symmetric with the right child of node2, AND b. The right child of node1 is symmetric with the left child of node2.
  5. Call the helper with root.left and root.right.

Pseudocode

function isSymmetrical(root):
    if root is null:
        return true
    return isMirror(root.left, root.right)

function isMirror(left, right):
    if left is null and right is null:
        return true
    if left is null or right is null:
        return false
    if left.value != right.value:
        return false
    return isMirror(left.left, right.right)
       and isMirror(left.right, right.left)

Time & Space Complexity

  • Time: O(n) where n is the number of nodes. Each node is visited once as part of a pair comparison.
  • Space: O(h) where h is the height of the tree, for the recursion stack. Worst case O(n) for a skewed tree.

Key Insights

  • The mirrored comparison crosses subtree boundaries: left.left pairs with right.right, and left.right pairs with right.left.
  • An iterative approach using a queue (BFS) or stack (DFS) is also possible, enqueueing/pushing pairs of nodes to compare.
  • Symmetry is strictly about structure and values, not about the tree being a BST.
  • This is different from checking if two trees are identical; the mirror relationship reverses left and right.

Edge Cases

  • Empty tree: symmetric (return true).
  • Single node: symmetric (no children to compare).
  • Root with only a left child or only a right child: not symmetric.
  • Tree with all identical values but asymmetric structure: not symmetric.
  • Perfect binary tree with all identical values: symmetric.
  • Tree where the first level is symmetric but deeper levels are not.

Linked mentions