☕ DSA Java Articles

Topics › Binary Trees › Medium Problems

Symmetric Binary Tree

Medium TUF ID 2784 A2ZSDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given the root of a binary tree. Decide whether the tree is symmetric: a mirror image of itself around a vertical line through the root. In other words, if you flip the tree left to right, you get exactly the same tree back, with the same shape and the same values in the same places.

An empty tree and a single node are symmetric. Constraints: up to 10^5 nodes (LeetCode allows 1000); values are integers.

Example 1

        1
      /   \
     2     2
    / \   / \
   3   4 4   3

answer = true

The left subtree read left to right is 3, 4 and the right subtree read right to left is 3, 4 as well.

Example 2

      1
    /   \
   2     2
    \     \
     3     3

answer = false

The values match level by level, but both 3s are right children. In the mirror image, the right subtree’s 3 would have to be a left child.

Approach 1: Serialize the tree both ways

Intuition. A tree is symmetric exactly when it equals its own mirror image. Comparing two trees is easy if we turn each into a list. A preorder traversal that writes a marker for every missing child describes a tree completely: two trees have the same marked preorder if and only if they are identical.

We do not even need to build the mirror. The preorder of the mirror image is just the preorder of the original that visits the right child before the left one. So we serialize the tree twice, once left-first and once right-first, and compare the lists.

The null markers are essential. Without them, the tree 1 with only a left child 2 serializes as [1, 2] both ways, and we would wrongly call it symmetric. With markers the two lists are [1, 2, null, null, null] and [1, null, 2, null, null], which differ.

Algorithm.

  1. Serialize with left-first preorder, writing null for missing children.
  2. Serialize with right-first preorder in the same way.
  3. Return whether the two lists are equal.
static boolean bruteForce(TreeNode root) {
    List<Integer> leftFirst = new ArrayList<>(), rightFirst = new ArrayList<>();
    serialize(root, true, leftFirst);
    serialize(root, false, rightFirst);
    return leftFirst.equals(rightFirst);
}

static void serialize(TreeNode node, boolean leftFirst, List<Integer> out) {
    if (node == null) { out.add(null); return; }              // the null marker keeps the shape in the list
    out.add(node.val);
    serialize(leftFirst ? node.left : node.right, leftFirst, out);
    serialize(leftFirst ? node.right : node.left, leftFirst, out);
}

Complexity. Time O(n): two traversals plus one list comparison. Space O(n) for the two lists (each holds 2n + 1 entries) plus O(h) recursion.

The cost is not the time but the memory, and the fact that it always reads the whole tree even when the very first pair of children differs.

Approach 2: Recursive mirror check

Intuition. Compare the two halves directly. The root’s left subtree a and right subtree b must be mirror images of each other. Two trees a and b are mirrors when:

If exactly one of them is empty, they are not mirrors. This definition is recursive and translates line by line into code. It stops at the first mismatch, so an asymmetric tree is often rejected after looking at only a few nodes.

Algorithm.

  1. If the root is null, return true.
  2. Return isMirror(root.left, root.right).
  3. In isMirror(a, b): if either is null, return a == b (true only when both are null). Otherwise check the values, then the outer pair, then the inner pair.
static boolean recursive(TreeNode root) {
    return root == null || isMirror(root.left, root.right);
}

static boolean isMirror(TreeNode a, TreeNode b) {
    if (a == null || b == null) return a == b;                // both missing is fine, exactly one missing is not
    return a.val == b.val && isMirror(a.left, b.right) && isMirror(a.right, b.left);
}

Dry run on Example 2:

call a b result
isMirror(2, 2) 2 2 values equal, check outer pair
isMirror(2.left, 2.right) null 3 exactly one is null: false
back in isMirror(2, 2)     && short-circuits: false

Complexity. Time O(n): each pair of mirrored nodes is compared once. Space O(h) for the recursion stack.

Approach 3: Iterative with a queue of pairs

Intuition. The recursion compares pairs of nodes. We can keep those pairs in a queue instead of on the call stack. Push the root’s two children as a pair. Each time we pop a pair (a, b): if both are null, the pair is fine; if one is null or the values differ, the tree is not symmetric; otherwise push the outer pair (a.left, b.right) and the inner pair (a.right, b.left).

One Java detail: ArrayDeque throws a NullPointerException when you add null, and our pairs often contain null. LinkedList accepts null elements, so it is the right queue here. Since we always add two entries at a time and pop two at a time, the pairing never gets out of step.

Algorithm.

  1. If the root is null, return true.
  2. Enqueue root.left and root.right.
  3. While the queue is not empty: pop a and b. Skip if both are null. Return false if one is null or a.val != b.val. Otherwise enqueue a.left, b.right, a.right, b.left.
  4. Return true.
static boolean iterative(TreeNode root) {
    if (root == null) return true;
    Queue<TreeNode> q = new LinkedList<>();                   // LinkedList accepts null entries; ArrayDeque does not
    q.add(root.left);
    q.add(root.right);
    while (!q.isEmpty()) {
        TreeNode a = q.poll(), b = q.poll();                  // entries always come in mirrored pairs
        if (a == null && b == null) continue;
        if (a == null || b == null || a.val != b.val) return false;
        q.add(a.left);
        q.add(b.right);
        q.add(a.right);
        q.add(b.left);
    }
    return true;
}

Complexity. Time O(n). Space O(w), where w is the widest level, because the queue holds pairs from at most two consecutive levels.

This version is the safest on very deep trees, where the recursion of Approaches 1 and 2 could overflow the Java call stack.

Edge cases and pitfalls