Symmetric Tree

Symmetric Tree asks if a tree is a mirror of itself. Picture folding the tree down the middle. Do the two halves line up? The interviewer wants to see if you can compare two sides in mirror order, not the same order.

🎯 The Problem

You get a binary tree. You have to say if it is a mirror of itself.

• A binary tree is a structure where each node has a value and up to two children.
• Symmetric means the left side is a mirror image of the right side.
• A mirror flips left and right.
• So the left child of the left side should match the right child of the right side.
• The crossing is the part people get wrong. You compare left to right, not left to left.

Input:
       1
      / \
     2   2
    / \ / \
   3  4 4  3

Output: true

Explanation: The left half mirrors the right half exactly.

Here is the tree. Fold it down the center and the two sides match.

🐢 Approach 1: Build a Mirror Copy and Compare (Brute Force)

The idea in one line: flip the whole tree, then check if the flip equals the original.

The idea:

• Build a copy of the tree with every node’s left and right children swapped.
• Compare that flipped copy with the original using a Same Tree check.
• If they match, the tree is symmetric.

How it works:

• Walk the whole tree once to build the flipped copy.
• Walk both trees together to check they are equal.

Why it is weak:

• You hold a full second copy of the tree in memory.
• That is O(n) extra space for nothing.
• You also do two full walks instead of one.

Here is the mirror-copy code:

def is_symmetric(root):
    def mirror(node):
        if not node: return None
        copy = TreeNode(node.val)
        copy.left = mirror(node.right)
        copy.right = mirror(node.left)
        return copy
    def same(a, b):
        if not a or not b: return a is b
        return a.val == b.val and same(a.left, b.left) and same(a.right, b.right)
    return same(root, mirror(root))

⚡ Approach 2: Direct Mirror Compare (Best)

The idea in one line: compare the left side and right side directly, in mirror order, with no copy.

The idea:

• Write one helper mirror(a, b) that asks “are these two a mirror of each other?”
• Mirror order means outer edges go together and inner edges go together.
• No extra tree. Just two pointers walking down together.

How it works:

• Both empty means they match. Return true.
• Only one empty means the shapes differ. Return false.
• Different values mean the mirror breaks. Return false.
• Recurse on the outer pair: left node’s left child with right node’s right child.
• Recurse on the inner pair: left node’s right child with right node’s left child.

Why it is fast:

• One walk, each node visited once. Time is O(n).
• The only extra memory is the recursion stack, O(h) for tree height h.

Here is the direct mirror-compare code:

def is_symmetric(root):
    def mirror(a, b):
        if not a or not b: return a is b
        return a.val == b.val and mirror(a.left, b.right) and mirror(a.right, b.left)
    return mirror(root.left, root.right) if root else True

🔁 Approach 3: Iterative With a Queue (Alternative)

The idea in one line: same crossing compare, written as a loop instead of recursion.

The idea:

• A queue is a line where you add at the back and remove from the front.
• Push node pairs that should mirror each other.

How it works:

• Start by pushing the pair (root.left, root.right).
• Pop a pair, compare values and empty cases.
• Push the outer pair and the inner pair back in.
• Stop the moment any pair fails.

Why you might pick it:

• It avoids deep recursion on a very tall tree.
• Same time and space as the recursive version.

The diagram below shows which pairs get compared. Notice the crossing arrows.

Steps to Solve

1. An empty tree is symmetric, so return true.
2. Write a helper mirror(a, b) for two nodes.
3. If both are empty, return true.
4. If only one is empty, return false.
5. If their values differ, return false.
6. Recurse on the outer pair: a.left with b.right.
7. Recurse on the inner pair: a.right with b.left.
8. Start by calling mirror(root.left, root.right).

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int val;
    struct Node *left;
    struct Node *right;
} Node;

Node *newNode(int val) {
    Node *n = (Node *)malloc(sizeof(Node));
    n->val = val;
    n->left = NULL;
    n->right = NULL;
    return n;
}

// are a and b mirror images of each other?
int mirror(Node *a, Node *b) {
    if (a == NULL && b == NULL) return 1;   // both empty
    if (a == NULL || b == NULL) return 0;   // one empty
    if (a->val != b->val) return 0;         // values differ
    return mirror(a->left, b->right)        // outer pair
        && mirror(a->right, b->left);       // inner pair (crossed)
}

int isSymmetric(Node *root) {
    if (root == NULL) return 1;
    return mirror(root->left, root->right);
}

int main(void) {
    Node *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(2);
    root->left->left = newNode(3);
    root->left->right = newNode(4);
    root->right->left = newNode(4);
    root->right->right = newNode(3);

    printf("%s\n", isSymmetric(root) ? "true" : "false");
    return 0;
}

true

#include <iostream>
using namespace std;

struct Node {
    int val;
    Node *left;
    Node *right;
    Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

bool mirror(Node *a, Node *b) {
    if (a == nullptr && b == nullptr) return true;  // both empty
    if (a == nullptr || b == nullptr) return false; // one empty
    if (a->val != b->val) return false;             // values differ
    return mirror(a->left, b->right)                // outer pair
        && mirror(a->right, b->left);               // inner pair
}

bool isSymmetric(Node *root) {
    if (root == nullptr) return true;
    return mirror(root->left, root->right);
}

int main() {
    Node *root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(2);
    root->left->left = new Node(3);
    root->left->right = new Node(4);
    root->right->left = new Node(4);
    root->right->right = new Node(3);

    cout << (isSymmetric(root) ? "true" : "false") << endl;
    return 0;
}

true

public class Symmetric {
    static class Node {
        int val;
        Node left, right;
        Node(int v) { val = v; }
    }

    static boolean mirror(Node a, Node b) {
        if (a == null && b == null) return true;   // both empty
        if (a == null || b == null) return false;  // one empty
        if (a.val != b.val) return false;          // values differ
        return mirror(a.left, b.right)             // outer pair
            && mirror(a.right, b.left);            // inner pair
    }

    static boolean isSymmetric(Node root) {
        if (root == null) return true;
        return mirror(root.left, root.right);
    }

    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(2);
        root.left.left = new Node(3);
        root.left.right = new Node(4);
        root.right.left = new Node(4);
        root.right.right = new Node(3);

        System.out.println(isSymmetric(root));
    }
}

true

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


def is_symmetric(root):
    def mirror(a, b):
        if a is None and b is None:    # both empty: match
            return True
        if a is None or b is None:     # one empty: differ
            return False
        if a.val != b.val:             # values differ
            return False
        return mirror(a.left, b.right) and \
            mirror(a.right, b.left)    # outer pair, then inner pair

    if root is None:
        return True
    return mirror(root.left, root.right)


root = Node(1)
root.left = Node(2)
root.right = Node(2)
root.left.left = Node(3)
root.left.right = Node(4)
root.right.left = Node(4)
root.right.right = Node(3)

print(is_symmetric(root))

True

class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function isSymmetric(root) {
  function mirror(a, b) {
    if (a === null && b === null) return true;  // both empty
    if (a === null || b === null) return false; // one empty
    if (a.val !== b.val) return false;          // values differ
    return mirror(a.left, b.right)              // outer pair
      && mirror(a.right, b.left);               // inner pair
  }

  if (root === null) return true;
  return mirror(root.left, root.right);
}

const root = new Node(1);
root.left = new Node(2);
root.right = new Node(2);
root.left.left = new Node(3);
root.left.right = new Node(4);
root.right.left = new Node(4);
root.right.right = new Node(3);

console.log(isSymmetric(root));

true

Let us walk through the Python version line by line so the crossing is clear.

The inner mirror function takes two nodes that should be mirror images. It starts with if a is None and b is None: return True. If both sides ran out at the same spot, they mirror fine. This is the base case.

Next, if a is None or b is None: return False. We know they are not both empty. So if one is empty now, the shapes do not mirror. We stop.

Then if a.val != b.val: return False. Both nodes exist. If their values are not equal, the mirror breaks right here.

Now the important line: return mirror(a.left, b.right) and mirror(a.right, b.left). This is the crossing. We pair the left node’s left child with the right node’s right child. That is the outer edges. Then we pair the left node’s right child with the right node’s left child. That is the inner edges. Both pairings must come back true.

Outside the helper, if root is None: return True handles an empty tree. Then return mirror(root.left, root.right) kicks off the check by mirroring the two halves under the root.

⏱️ Time and Space Complexity

The mirror check visits every node once, so the time is O(n). The recursion uses memory for the call stack, which goes as deep as the tree is tall. So the space is O(h), where h is the height of the tree. The build-a-copy way also takes O(n) time but needs O(n) extra space for the copy.

🧩 Key Takeaways

• ✅ Symmetric means the left side is a mirror image of the right side.
• ✅ Compare in mirror order, not the same order, so left to right crossed.
• ✅ Pair outer children together and inner children together at each step.
• ✅ Check the empty cases before reading any value, or the code crashes.
• ✅ The direct check is O(n) time and O(h) space, with no extra copy.

🚀 What’s Next?

• Same Tree
• Balanced Binary Tree