☕ DSA Java Articles

Topics › Binary Trees › Medium Problems

Check for symmetrical BTs

Medium TUF ID 128 SDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Given the root of a binary tree, decide whether it is symmetric, meaning it is a mirror image of itself around a vertical line through the root. Formally, the tree is symmetric when its left subtree is the mirror of its right subtree, where two trees A and B are mirrors of each other if

An empty tree and a single node are symmetric.

Constraints (LeetCode 101): 1 to 1000 nodes, values in [-100, 100]. The Java file also runs a 131071-node tree.

Example 1

        1
      /   \
     2     2
    / \   / \
   3   4 4   3
answer = true

Fold the picture along the vertical line through 1: every node lands on a node with the same value.

Example 2

      1
     / \
    2   2
     \   \
      3   3
answer = false

Each level reads the same forwards and backwards if you only look at values (2 2, then 3 3), yet the tree is not symmetric: both 3s are right children, and the mirror of a right child is a left child. Symmetry is about shape and values together.

Approach 1: Build the mirror and compare

Intuition. “Symmetric” means “equal to its own mirror image”. So construct that mirror image explicitly: a copy of the tree in which every node’s children are swapped. Then check whether the original and the copy are identical, node by node. This is a direct translation of the definition and is easy to trust, which makes it a good first solution and a good test oracle.

Algorithm.

  1. Build mirrorCopy(root): a new node with the same value whose left child is the mirror copy of the original right child, and vice versa.
  2. Compare the original and the copy with the usual “identical trees” recursion: both null, or equal values with identical left subtrees and identical right subtrees.
static boolean mirrorAndCompare(TreeNode root) {
    return identical(root, mirrorCopy(root));
}

static TreeNode mirrorCopy(TreeNode node) {
    if (node == null) return null;
    TreeNode m = new TreeNode(node.val);
    m.left = mirrorCopy(node.right);                     // children swap sides at every level
    m.right = mirrorCopy(node.left);
    return m;
}

static boolean identical(TreeNode a, TreeNode b) {
    if (a == null || b == null) return a == b;
    return a.val == b.val && identical(a.left, b.left) && identical(a.right, b.right);
}

Complexity. Time O(n): the copy visits each node once and the comparison visits each node at most once. Space O(n) for the copied tree, plus O(h) recursion. It also does redundant work: comparing the tree with its mirror checks every left/right pair twice, once from each side.

Approach 2: Compare the two halves directly (recursive)

Intuition. We never need the whole mirror copy. The definition already says what to compare: the left subtree against the right subtree as mirrors. Walk both halves at the same time with two pointers a (in the left half) and b (in the right half). Mirroring swaps sides, so the outer pair a.left and b.right must mirror each other, and so must the inner pair a.right and b.left.

Each recursive call compares one node from the left half with the node that should be its reflection, so every node is looked at once and nothing is copied.

Algorithm.

  1. An empty tree is symmetric. Otherwise return isMirror(root.left, root.right).
  2. isMirror(a, b):
    • If either is null, the pair is fine only if both are null.
    • Otherwise require a.val == b.val, isMirror(a.left, b.right) and isMirror(a.right, b.left).
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)                 // outer pair
            && isMirror(a.right, b.left);                // inner pair
}

The line if (a == null || b == null) return a == b; covers three cases at once: both null gives true, and exactly one null gives false because a null reference never equals a real node.

Complexity. Time O(n): each node takes part in at most one comparison, and && stops at the first mismatch. Space O(h) for the recursion; no copy is made.

Approach 3: Same comparison with a queue (iterative)

Intuition. The recursion in Approach 2 is just a list of pairs still to be checked. We can keep those pairs in a queue instead of on the call stack. Start with the pair (root.left, root.right). Take a pair out; if both are null, it is fine; if exactly one is null or the values differ, the tree is not symmetric; otherwise add the outer pair and the inner pair. If the queue empties without a mismatch, the tree is symmetric.

A Java detail: ArrayDeque does not accept null elements, but we store arrays of two nodes. The array itself is never null, even when its entries are, so this is safe.

Algorithm.

  1. If the root is null, return true. Enqueue {root.left, root.right}.
  2. While the queue is not empty: dequeue {a, b}.
    • Both null: continue.
    • One null, or a.val != b.val: return false.
    • Otherwise enqueue {a.left, b.right} and {a.right, b.left}.
  3. Return true.
static boolean iterative(TreeNode root) {
    if (root == null) return true;
    Deque<TreeNode[]> queue = new ArrayDeque<>();
    queue.add(new TreeNode[]{root.left, root.right});
    while (!queue.isEmpty()) {
        TreeNode[] pair = queue.poll();
        TreeNode a = pair[0], b = pair[1];
        if (a == null && b == null) continue;
        if (a == null || b == null || a.val != b.val) return false;
        queue.add(new TreeNode[]{a.left, b.right});
        queue.add(new TreeNode[]{a.right, b.left});
    }
    return true;
}

Dry run on Example 2 (L and R are the left and right 2):

dequeued pair check enqueued
(L, R) both 2, equal (L.left = null, R.right = 3), (L.right = 3, R.left = null)
(null, 3) exactly one is null stop, return false

Complexity. Time O(n). Space O(w), where w is the maximum width, because the queue holds about one level of pairs at a time. Using a stack instead of a queue would also work and would use O(h) space instead; the order in which pairs are checked does not matter, only that every pair is checked.

Edge cases and pitfalls