Mirrored binary tree tester

You're in a Facebook interview when the interviewer draws two binary trees on the whiteboard and asks, "Can you tell me if these two trees are mirror images of each other?" At first glance, the trees look similar but subtly different. The left and right children seem swapped. This problem, also known as "Check if Two Trees are Mirror Images" on other platforms, tests your ability to reason about tree structure recursively and handle multiple base cases cleanly. It's a favorite at companies like Facebook and Bloomberg because it reveals whether a candidate truly understands how binary trees work.

TL;DR

Two binary trees are mirrors if they share the same root value and each tree's left subtree mirrors the other tree's right subtree. The recursive solution checks three base cases (both null, one null, values differ) then recurses on cross-paired subtrees: t1.left with t2.right and t1.right with t2.left. This runs in O(n) time and O(n) space in the worst case due to the call stack.

Why This Problem Matters

The mirrored binary tree problem sits at the intersection of recursion and tree traversal, two concepts that come up in almost every tree-related interview question. If you can reason about how two trees relate to each other structurally, you can tackle problems like symmetric tree detection, tree serialization comparison, and subtree matching. Companies use this as a stepping stone: solve the mirror check, and the interviewer often follows up with "Now, can you convert a tree into its mirror?"

Binary Trees Refresher

A binary tree is a data structure where each node has at most two children. Here's a quick visual to set the stage:

Key terms:

• Root: The topmost node (node 1 above)
• Leaf: A node with no children (nodes 2, 4, and 5 above)
• Subtree: Any node and all its descendants form a subtree

The idea of mirroring is straightforward: if you placed a vertical mirror next to one tree, its reflection should produce the other tree.

Understanding the Problem

Given: The root nodes of two binary trees, t1 and t2 Task: Determine if the trees are mirror images of each other Return: true if they are mirrors, false otherwise Constraints: Both trees have at least 1 and at most 1000 nodes. Node values range from 0 to 1000.

Here's the example from the problem. Tree 1 (t1):

Tree 2 (t2):

Notice how t1's left child (2) appears as t2's right child, and t1's right subtree (3 with children 4, 5) appears flipped on the left side of t2 (3 with children 5, 4). That's the mirror relationship: left maps to right, and right maps to left, at every level.

When Trees Are NOT Mirrors

Not every pair of trees with the same values qualifies. Consider this pair where the structure looks similar but the leaf values don't line up correctly:

Tree A:

Tree B:

For these to be mirrors, t1's left subtree [2, 4, 5] would need to match t2's right subtree [2, 5, 7]. But 4 does not equal 7, so this pair fails the mirror check.

Edge Cases

1. Both trees are a single node with the same value: They are mirrors (trivially).
2. One tree is null and the other is not: Not mirrors. The structures don't match.
3. Both null: Mirrors (two empty trees reflect each other perfectly).
4. Same values, different structure: Not mirrors. Structure matters just as much as values.

Solution Approach

Let's think about what it means to be a mirror, starting from the roots and working down.

At the root level, both trees must have the same value. Then for the mirror property to hold at the next level, t1.left must mirror t2.right, and t1.right must mirror t2.left. This pattern repeats all the way down to the leaves.

This naturally gives us a recursive definition:

1. If both nodes are null, they are mirrors (base case).
2. If only one is null, they are not mirrors (structural mismatch).
3. If their values differ, they are not mirrors.
4. Otherwise, recursively check that t1.left mirrors t2.right AND t1.right mirrors t2.left.

The critical insight is step 4: we cross-pair the subtrees. This is what distinguishes mirror checking from identical-tree checking, where you'd compare left-with-left and right-with-right.

Pro tip: Draw the recursive calls on the whiteboard during your interview. It makes the cross-pairing logic immediately clear and shows the interviewer you can trace through your own code.

Implementation

Prefer a different language? Jump to solutions in other languages.

public class Solution {
  public Boolean areMirrored(TreeNode t1, TreeNode t2) {
    // Base case: two empty trees are mirrors
    if (t1 == null && t2 == null) return true;

    // Structural mismatch: one is null, the other is not
    else if (t1 == null || t2 == null) return false;

    // Value mismatch at the current level
    else if (t1.data != t2.data) return false;

    // Cross-pair the subtrees: left-with-right, right-with-left
    else return areMirrored(t1.left, t2.right) &&
                  areMirrored(t1.right, t2.left);
  }
}

Tracing the Recursion

Let's trace through the main example where t1 = 1 2 3 # # 4 5 and t2 = 1 3 2 5 4 # #:

The recursion fans out from the root, cross-comparing subtrees at each level. Every leaf-level call hits the "both null" base case and returns true. The results propagate upward: true && true = true at each internal node, giving us a final answer of true.

Step-by-Step Walkthrough

Here's how the algorithm processes each call:

1. areMirrored(1, 1): Values match. Recurse on (t1.left=2, t2.right=2) and (t1.right=3, t2.left=3).
2. areMirrored(2, 2): Values match. Both children are null on both sides. Returns true && true = true.
3. areMirrored(3, 3): Values match. Recurse on (t1.left=4, t2.right=4) and (t1.right=5, t2.left=5).
4. areMirrored(4, 4): Values match. Leaf nodes. Returns true.
5. areMirrored(5, 5): Values match. Leaf nodes. Returns true.
6. Back at step 3: true && true = true.
7. Back at step 1: true && true = true. Final answer: true.

Complexity Analysis

Time Complexity: O(n)

Every node in both trees is visited at most once. If the trees have n nodes total, the algorithm makes O(n) comparisons. In practice, it can be faster: if a mismatch is found early (say, at the root), the algorithm returns false immediately without visiting the remaining nodes.

Space Complexity: O(n)

The space comes from the recursive call stack. In the worst case, both trees are completely skewed (all nodes on one side), creating a call stack n levels deep. For balanced trees, the depth is O(log n). The problem states trees can have up to 1000 nodes, so stack overflow is not a concern here.

Comparison with Identical Tree Check

The only difference is how the subtrees are paired in the recursive calls. Everything else is the same.

Common Pitfalls

1. Comparing left-with-left instead of left-with-right: This is the most frequent mistake. You end up solving "identical trees" instead of "mirrored trees."

2. Forgetting the single-null base case: If you only check t1 == null && t2 == null, you'll get a NullPointerException when one node is null and the other isn't.

3. Checking structure but not values: Two trees can have the same shape but different values. Both structure AND values must match for the mirror property.

4. Short-circuit evaluation confusion: In Java, && short-circuits. If the first recursive call returns false, the second call never executes. This is correct behavior, but make sure you understand it when tracing through your solution.

Interview Tips

When you encounter this problem in an interview:

1. Clarify the definition: Ask whether "mirror" means structural mirror with matching values, or just structural mirror. Most interviewers mean both.

2. Start with the base cases: There are three. Enumerate them explicitly before writing any recursive logic. This shows discipline.

3. Draw two small trees: Use 3-4 nodes each. Trace through the cross-pairing by hand. Interviewers love seeing you validate your approach visually.

4. Mention the iterative alternative: After presenting the recursive solution, briefly mention that you could use a queue-based BFS approach. This demonstrates breadth of knowledge.

5. Discuss the connection to symmetric trees: If the interviewer asks for a follow-up, checking whether a single tree is symmetric is just areMirrored(root.left, root.right).

Key Takeaways

• Two trees are mirrors when their root values match and each tree's left subtree mirrors the other's right subtree, checked recursively.
• The three base cases (both null, one null, values differ) must all be handled before the recursive step. Missing any one of them introduces bugs.
• The only difference between checking for identical trees and mirrored trees is the subtree pairing: identical uses left-left/right-right, mirrored uses left-right/right-left.
• Time complexity is O(n) since every node is visited once. Space complexity is O(n) in the worst case due to the recursive call stack on skewed trees.
• This problem is a building block for symmetric tree detection. If you can check mirrors between two trees, checking symmetry within one tree is a one-line extension.

Solutions in Other Languages

Python

class Solution:
    def are_mirrored(self, t1: TreeNode, t2: TreeNode) -> bool:
        if t1 is None and t2 is None:
            return True
        elif t1 is None or t2 is None:
            return False
        elif t1.data != t2.data:
            return False
        else:
            return self.are_mirrored(t1.left, t2.right) and \
                   self.are_mirrored(t1.right, t2.left)

JavaScript

class Solution {
  areMirrored(t1, t2) {
    if (t1 === null && t2 === null) return true;
    else if (t1 === null || t2 === null) return false;
    else if (t1.data !== t2.data) return false;
    else return this.areMirrored(t1.left, t2.right) &&
        this.areMirrored(t1.right, t2.left);
  }
}

TypeScript

class Solution {
    areMirrored(t1: TreeNode | null, t2: TreeNode | null): boolean {
        if (t1 === null && t2 === null) return true;
        else if (t1 === null || t2 === null) return false;
        else if (t1.data !== t2.data) return false;
        else return this.areMirrored(t1.left, t2.right) &&
            this.areMirrored(t1.right, t2.left);
    }
}

C++

class Solution {
public:
  bool areMirrored(TreeNode *t1, TreeNode *t2) {
    if (t1 == nullptr && t2 == nullptr) return true;
    else if (t1 == nullptr || t2 == nullptr) return false;
    else if (t1->data != t2->data) return false;
    else
      return areMirrored(t1->left, t2->right) &&
             areMirrored(t1->right, t2->left);
  }
};

Go

func (s *Solution) AreMirrored(t1 *TreeNode, t2 *TreeNode) bool {
    if t1 == nil && t2 == nil {
        return true
    } else if t1 == nil || t2 == nil {
        return false
    } else if t1.Data != t2.Data {
        return false
    } else {
        return s.AreMirrored(t1.Left, t2.Right) &&
            s.AreMirrored(t1.Right, t2.Left)
    }
}

Scala

class Solution {
  def areMirrored(t1: TreeNode, t2: TreeNode): Boolean = {
    if (t1 == null && t2 == null) true
    else if (t1 == null || t2 == null) false
    else if (t1.data != t2.data) false
    else areMirrored(t1.left, t2.right) && areMirrored(t1.right, t2.left)
  }
}

Kotlin

class Solution {
    fun areMirrored(t1: TreeNode?, t2: TreeNode?): Boolean {
        if (t1 == null && t2 == null) return true
        else if (t1 == null || t2 == null) return false
        else if (t1.data != t2.data) return false
        else return areMirrored(t1.left, t2.right) &&
                      areMirrored(t1.right, t2.left)
    }
}

Swift

class Solution {
    func areMirrored(_ t1: TreeNode?, _ t2: TreeNode?) -> Bool {
        if t1 == nil && t2 == nil { return true }
        else if t1 == nil || t2 == nil { return false }
        else if t1!.data != t2!.data { return false }
        else { return areMirrored(t1!.left, t2!.right) &&
                      areMirrored(t1!.right, t2!.left) }
    }
}

Ruby

class Solution
  def are_mirrored(t1, t2)
    return true if t1.nil? && t2.nil?
    return false if t1.nil? || t2.nil?
    return false if t1.data != t2.data
    are_mirrored(t1.left, t2.right) && are_mirrored(t1.right, t2.left)
  end
end

Rust

impl Solution {
    pub fn are_mirrored(&self, t1: Option<Box<TreeNode>>, t2: Option<Box<TreeNode>>) -> bool {
        if t1.is_none() && t2.is_none() {
            return true;
        }
        if t1.is_none() || t2.is_none() {
            return false;
        }
        let first = t1.unwrap();
        let second = t2.unwrap();
        if first.data != second.data {
            return false;
        }
        self.are_mirrored(first.left, second.right) &&
            self.are_mirrored(first.right, second.left)
    }
}

Dart

class Solution {
  bool areMirrored(TreeNode? t1, TreeNode? t2) {
    if (t1 == null && t2 == null) return true;
    else if (t1 == null || t2 == null) return false;
    else if (t1.data != t2.data) return false;
    else return areMirrored(t1.left, t2.right) &&
                  areMirrored(t1.right, t2.left);
  }
}

PHP

class Solution {
    public function areMirrored(?TreeNode $t1, ?TreeNode $t2): bool {
        if ($t1 === null && $t2 === null) return true;
        if ($t1 === null || $t2 === null) return false;
        if ($t1->data !== $t2->data) return false;
        return $this->areMirrored($t1->left, $t2->right) &&
               $this->areMirrored($t1->right, $t2->left);
    }
}

C#

public class Solution {
    public bool AreMirrored(TreeNode? t1, TreeNode? t2) {
        if (t1 == null && t2 == null) return true;
        else if (t1 == null || t2 == null) return false;
        else if (t1.data != t2.data) return false;
        else return AreMirrored(t1.left, t2.right) &&
                      AreMirrored(t1.right, t2.left);
    }
}

Practice Makes Perfect

Now that you understand mirror checking, try these related problems to solidify your tree comparison skills:

• Identical Binary Trees - Compare left-with-left instead of cross-pairing
• Convert Binary Tree to Mirror - Transform a tree into its own mirror in-place
• Symmetric Tree - Check if a single tree is its own mirror

Consistent practice builds the pattern recognition you need for interview day. This problem and hundreds of other tree problems are available on Firecode, where over 50,000 engineers have prepared for technical interviews and landed roles at top tech companies. Whether you're targeting Facebook, Bloomberg, or any other company that loves tree questions, building fluency with recursive tree comparisons will pay dividends.