Why this matters
A mirror image is what you see in a mirror. Left and right swap places, and everything else stays the same. Trees have the same idea. If a tree has a node with a left child and a right child, its mirror image has those two children in the opposite order, at every level.
Mirror questions are common in interviews because they test recursion in a clean way. Each question asks you to treat two sides of a tree in a matching pattern. The same pattern shows up in later problems, such as checking whether two trees are the same, and in code that walks a tree from both ends at once.
This lesson covers three tasks. The first is to invert a tree, which means swapping the left and right child of every node. The second is to check whether one tree is the mirror image of another. The third is to check whether a single tree is symmetric, which means its left half is the mirror of its right half.
The lesson uses recursion, which means a function that calls itself on smaller parts of the tree. If recursion is new to you, read the recursion module first. It also uses std::unique_ptr, a pointer that owns the node it points to and frees it when the owner goes away. The previous lesson in this module introduced the same node type.
Mirror image in plain words
Take a tree with a root and two children, 2 and 3. The mirror image has the same root. Its left child is 3, and its right child is 2.
Original Mirror image
1 1
/ \ / \
2 3 3 2The values in the nodes stay the same. Only the sides change. If node 2 had children of its own, the mirror image would have those children swapped too, and so on down the tree.
Two words are used in this lesson.
- To invert a tree is to make its mirror image in place. You change the tree you have, so the result is the mirror.
- A tree is symmetric when its left side is a mirror image of its right side. The root is the middle line, and the two halves match when you fold the picture along it.
Start with the smallest case
A tree with one node has no children, so there is nothing to swap. Its mirror image is itself.
A tree with a root and two leaves is the next case. The root is 1. Its left child is 2, and its right child is 3. To invert it, swap the two children. Now the left child is 3 and the right child is 2. The mirror image has the same root and the children in reversed order.
A tree with a root and only one child is different. The root is 1, and it has a left child 2 and no right child. After inversion, the left child is empty and the right child is 2. The tree is now shaped like a mirror image, even though it has the same number of nodes.
This is the point that matters most. Inversion swaps two pointers at every node. It does not add or remove nodes. The values stay the same.
Example 1: invert one level
Here is a tree with five nodes. The root is 5. Its left child is 3, which has a left child 1. Its right child is 8, which has a right child 9.
5
/ \
3 8
/ \
1 9Inverting this tree changes the sides at each node. At the root, 3 moves to the right, and 8 moves to the left. At node 3, the child 1 moves to the right. At node 8, the child 9 moves to the left.
5
/ \
8 3
/ \
9 1The swap is one step per node. First the node swaps its two children. Then it does the same for the children that are now in its left and right positions. The recursion takes care of the rest.
Invert: swap the children at every node
Here is the rule for invert. Given a node, swap its left and right pointers. Then call invert on the new left child and the new right child. If the node is empty, do nothing.
void invert(Node* n) {
if (n == nullptr) return;
std::swap(n->left, n->right);
invert(n->left.get());
invert(n->right.get());
}The order matters. The code swaps first, then recurses. After the swap, n->left holds the old right child, and n->right holds the old left child. Both are visited, so every node in the tree is swapped exactly once.
The check if (n == nullptr) return; is needed because a leaf has two empty children. Calling invert on an empty pointer would crash, as the mistakes section shows.
Example 2: a deeper tree
Now take a tree with three levels below the root. Use the same rule at each node.
1
/ \
2 3
/ \ \
4 5 6Walk through the calls.
invert(1)swaps 2 and 3. The root now has 3 on the left and 2 on the right.invert(3)is the next call on the left. Node 3 had no left child and one right child, 6. After the swap, 6 is on its left.invert(6)is a leaf, so it swaps two empty pointers and does nothing useful.invert(2)is the call on the right. Node 2 had children 4 and 5. After the swap, 5 is on its left and 4 is on its right.invert(5)andinvert(4)are leaves, so they change nothing.
The result is the mirror image of the whole tree. The root is still 1, and every level is reversed.
Mirror check: compare two trees
Inversion changes one tree. The next task is to check whether two separate trees are mirror images of each other. You do not change either tree.
Two trees a and b are mirrors when these three things are true.
- Both nodes are empty, or both are non-empty.
- The values in the two nodes are the same.
- The left child of
amirrors the right child ofb, and the right child ofamirrors the left child ofb.
Rule 3 is the key idea. The left side of one tree must match the right side of the other. The sides cross over.
bool areMirrors(const Node* a, const Node* b) {
if (a == nullptr || b == nullptr) return a == b;
return a->val == b->val
&& areMirrors(a->left.get(), b->right.get())
&& areMirrors(a->right.get(), b->left.get());
}The line return a == b; handles the empty cases. If both are empty, the two pointers are equal, so the result is true. If only one is empty, the pointers are not equal, so the result is false.
Example 3: check a tree against its inverted copy
Build two copies of the same tree. Invert one of them. Then check whether the two copies are mirrors.
Original tree Copy, after invert
1 1
/ \ / \
2 2 2 2
/ \ / \ / \ / \
3 4 3 4 4 3 4 3The original's left child is 2, with a 3 on the left and a 4 on the right. Its right child is 2, with the same two children. Inverting the copy swaps the two sides at the root and swaps the children under each 2. So the copy's left child is 2 with a 4 on the left and a 3 on the right, and its right child is the same.
Rule 3 says the left of the first tree must match the right of the second. The original's left child is 2 with a 3 on the left. The copy's right child is 2 with a 3 on the right. The 3s match, and the 4s match too. So the two trees are mirrors, and the check prints true.
A tree is always the mirror of its own inverted copy. The check is useful because it tests the inversion code: if invert misses a node, the check fails.
Symmetry: a tree against itself
A tree is symmetric when its left side mirrors its right side. The check is the same as the mirror check, but both trees are parts of the same tree. You pass the root's left child and the root's right child to areMirrors.
bool isSymmetric(const Node* root) {
if (root == nullptr) return true;
return areMirrors(root->left.get(), root->right.get());
}An empty tree counts as symmetric, because there is nothing to compare. A tree with only a root is also symmetric, because both sides are empty.
Example 4: a symmetric tree with mixed values
1
/ \
2 2
/ \ / \
3 4 4 3The root is 1. The left child is 2, with a 3 on the left and a 4 on the right. The right child is 2, with a 4 on the left and a 3 on the right. Each 3 matches the other 3 in the opposite position, and each 4 matches the other 4. This tree is symmetric.
Example 5: a tree that looks balanced but is not symmetric
1
/ \
2 2
/ \ / \
3 4 3 4The shape is the same as Example 4, but the values are in the same order on both sides. The two 3s are both on the left of their parents, so they do not face each other across the root. This tree is not symmetric.
The check finds the problem one level below those two children. The left child of the root is 2, and the right child is 2. Their values match. Then the left child of the left 2 is 3, and the right child of the right 2 is 4. The values differ, so the check returns false.
The iterative version with a queue
areMirrors uses recursion. You can also do the symmetry check with a queue, which is a first-in, first-out line of waiting items. The queue holds pairs of nodes that must mirror each other. Each step takes one pair off the front and checks it. If the pair matches, it adds two new pairs to the back: the outer children, and the inner children.
bool isSymmetricIterative(const Node* root) {
if (root == nullptr) return true;
std::queue<std::pair<const Node*, const Node*>> q;
q.push({root->left.get(), root->right.get()});
while (!q.empty()) {
auto [a, b] = q.front();
q.pop();
if (a == nullptr && b == nullptr) continue;
if (a == nullptr || b == nullptr) return false;
if (a->val != b->val) return false;
q.push({a->left.get(), b->right.get()});
q.push({a->right.get(), b->left.get()});
}
return true;
}The queue version is useful when a tree is very deep, because the recursion depth grows with the height of the tree. A deep tree can use up the call stack. The queue uses heap memory instead. For most small trees, both versions are fine.
The pair (a, b) is the same as the recursive call areMirrors(a, b). The queue just replaces the call stack with a list.
The full program
The program below builds the trees from the examples and prints the results. It uses the node type from the previous lesson. The dump function prints the tree in preorder, which means it prints each node before its children. A missing child prints as a dot, so the output shows the shape of the tree as well as the values.
#include <iostream>
#include <memory>
#include <queue>
#include <utility>
struct Node {
int val;
std::unique_ptr<Node> left;
std::unique_ptr<Node> right;
explicit Node(int v) : val(v) {}
};
std::unique_ptr<Node> make(int v, std::unique_ptr<Node> l = nullptr, std::unique_ptr<Node> r = nullptr) {
auto n = std::make_unique<Node>(v);
n->left = std::move(l);
n->right = std::move(r);
return n;
}
// Prints the tree in preorder (node, left, right). A missing child prints as a dot.
void dump(const Node* n) {
if (n == nullptr) {
std::cout << ". ";
return;
}
std::cout << n->val << ' ';
dump(n->left.get());
dump(n->right.get());
}
// Swaps the left and right children of every node.
void invert(Node* n) {
if (n == nullptr) return;
std::swap(n->left, n->right);
invert(n->left.get());
invert(n->right.get());
}
// True when the tree at b is the mirror image of the tree at a.
bool areMirrors(const Node* a, const Node* b) {
if (a == nullptr || b == nullptr) return a == b;
return a->val == b->val
&& areMirrors(a->left.get(), b->right.get())
&& areMirrors(a->right.get(), b->left.get());
}
// A tree is symmetric when its left subtree mirrors its right subtree.
bool isSymmetric(const Node* root) {
if (root == nullptr) return true;
return areMirrors(root->left.get(), root->right.get());
}
// Same check, written with a queue of pairs instead of recursion.
bool isSymmetricIterative(const Node* root) {
if (root == nullptr) return true;
std::queue<std::pair<const Node*, const Node*>> q;
q.push({root->left.get(), root->right.get()});
while (!q.empty()) {
auto [a, b] = q.front();
q.pop();
if (a == nullptr && b == nullptr) continue;
if (a == nullptr || b == nullptr) return false;
if (a->val != b->val) return false;
q.push({a->left.get(), b->right.get()});
q.push({a->right.get(), b->left.get()});
}
return true;
}
// Wrong on purpose: pairs the left children with the left children.
bool isSameDirection(const Node* a, const Node* b) {
if (a == nullptr || b == nullptr) return a == b;
return a->val == b->val
&& isSameDirection(a->left.get(), b->left.get())
&& isSameDirection(a->right.get(), b->right.get());
}
bool isSymmetricWrong(const Node* root) {
if (root == nullptr) return true;
return isSameDirection(root->left.get(), root->right.get());
}
// A symmetric tree with a mix of values on both sides.
// Root 1. Its two children are 2. Under each 2 are a 3 and a 4, in mirrored order.
std::unique_ptr<Node> symmetricSample() {
return make(1,
make(2, make(3), make(4)),
make(2, make(4), make(3)));
}
// Not symmetric: both 3s are on the left side of their parents.
// Root 1. Its two children are 2. Under each 2 are a 3 on the left and a 4 on the right.
std::unique_ptr<Node> asymmetricSample() {
return make(1,
make(2, make(3), make(4)),
make(2, make(3), make(4)));
}
int main() {
auto s = symmetricSample();
std::cout << "symmetric sample, preorder: ";
dump(s.get());
std::cout << "\n";
std::cout << "isSymmetric: " << std::boolalpha << isSymmetric(s.get()) << "\n";
std::cout << "isSymmetricIterative: " << isSymmetricIterative(s.get()) << "\n";
auto a = asymmetricSample();
std::cout << "asymmetric sample, preorder: ";
dump(a.get());
std::cout << "\n";
std::cout << "isSymmetric: " << isSymmetric(a.get()) << "\n";
std::cout << "isSymmetricIterative: " << isSymmetricIterative(a.get()) << "\n";
std::cout << "isSymmetricWrong (buggy): " << isSymmetricWrong(a.get()) << "\n";
// Invert a copy of the asymmetric tree. The result is the mirror of the original.
auto b = asymmetricSample();
invert(b.get());
std::cout << "inverted, preorder: ";
dump(b.get());
std::cout << "\n";
std::cout << "areMirrors(original, inverted): " << areMirrors(a.get(), b.get()) << "\n";
std::cout << "areMirrors(original, original): " << areMirrors(a.get(), a.get()) << "\n";
// Inverting twice gives back the original shape.
invert(b.get());
std::cout << "inverted twice, preorder: ";
dump(b.get());
std::cout << "\n";
// A symmetric tree is its own mirror image, so inverting it gives the same preorder output.
invert(s.get());
std::cout << "symmetric after invert, preorder: ";
dump(s.get());
std::cout << "\n";
return 0;
}Compile it with these flags and run it.
g++ -std=c++20 -Wall -o mirror14 mirror14.cpp
./mirror14The output is:
symmetric sample, preorder: 1 2 3 . . 4 . . 2 4 . . 3 . .
isSymmetric: true
isSymmetricIterative: true
asymmetric sample, preorder: 1 2 3 . . 4 . . 2 3 . . 4 . .
isSymmetric: false
isSymmetricIterative: false
isSymmetricWrong (buggy): true
inverted, preorder: 1 2 4 . . 3 . . 2 4 . . 3 . .
areMirrors(original, inverted): true
areMirrors(original, original): false
inverted twice, preorder: 1 2 3 . . 4 . . 2 3 . . 4 . .
symmetric after invert, preorder: 1 2 3 . . 4 . . 2 4 . . 3 . .Read the output line by line. The symmetric sample passes both checks. The asymmetric sample fails both. The inverted copy is the mirror of the original, and inverting it twice restores the original preorder. The last line is the same as the first, because a symmetric tree is its own mirror.
Note that areMirrors(original, original) is false for the asymmetric tree. The tree is not a mirror of itself, because its left and right halves do not match.
Common mistakes
Comparing the same direction instead of crossing over
The most common error in symmetry checks is to compare the left child of the left side with the left child of the right side. That compares the tree with itself, not with its mirror. The buggy function in the program does this, and its output on the asymmetric sample is wrong:
isSymmetricWrong (buggy): trueThe correct answer is false, because the 3s are both on the left. The buggy function says true, because it lines up 3 with 3 and 4 with 4.
The buggy function also fails in the other direction. Take a tree with root 1, a left child 2 with a left child 3, and a right child 2 with a right child 3. This tree is symmetric, so the right answer is true. The buggy function compares the left 2's left child, which is 3, with the right 2's left child, which is empty. One side has a node and the other does not, so it returns false. The correct check returns true, and the buggy check returns false. The fix is to cross the sides: compare a->left with b->right, and a->right with b->left.
Treating a missing child as a match
When one child is empty and the other is not, the two sides cannot match. A common mistake is to return true when either pointer is null:
if (a == nullptr || b == nullptr) return true;With this line, a tree with a root 1, a left child 2, and no right child would be symmetric. That is wrong, because the left side has a node and the right side has none. The correct line is return a == b;. It returns true only when both are empty.
On the one-sided tree, the correct program prints isSymmetric: false. The buggy version prints isSymmetric: true.
Forgetting the null check in invert
If invert does not check for an empty pointer, the function crashes on the first leaf. A leaf has two empty children, so the recursive calls reach an empty node and try to read n->left. Reading through an empty pointer is a crash.
This small program has no null check, and it runs on a tree with just two nodes. It was built with AddressSanitizer, a tool that stops a program when it reads memory it should not, and it prints a report. The first lines of the report look like this:
AddressSanitizer:DEADLYSIGNAL
==207573==ERROR: AddressSanitizer: SEGV on unknown address 0x000000000008 (pc 0x5ca7e5b86f94 bp 0x7ffefadd4c40 sp 0x7ffefadd4bb0 T0)
==207573==The signal is caused by a READ memory access.
==207573==Hint: address points to the zero page.The address 0x8 is the offset of a field inside a node that is not there. The report also shows the function that crashed. The process ID after ==, and the pc, bp and sp addresses, change each time you run it. The fix is the first line of invert, if (n == nullptr) return;.
Inverting one side only
Inversion must change every node. A common bug is to swap the root's children and then stop, which leaves the lower levels in their old order. The recursive calls in invert are the part that handles lower levels. Remove them, and the output shows only the top level changed. Run dump before and after to see the difference.
Practice
Each exercise has its answer below it. Try each one before you read the answer.
Exercise 1: invert a small tree
Invert this tree, then write its preorder output with dots for empty children.
5
/ \
3 8
/ \
1 9Show the answer
The tree has root 5, left 3 with a left child 1, and right 8 with a right child 9. After inversion, the root's children are swapped. Node 8 now has 9 on its left, and node 3 now has 1 on its right. The preorder output is 5 8 9 . . . 3 . 1 . .. Build this tree in main and call dump to check.
Exercise 2: is this tree symmetric?
Root 1. Its left child is 2 with a child 3 on the left. Its right child is 2 with a child 3 on the right. Is the tree symmetric?
Show the answer
Yes. The left 2 has its 3 on the left, and the right 2 has its 3 on the right. Those two 3s are in mirrored places. The check isSymmetric returns true. The buggy same-direction check returns false, which is the wrong answer.
Exercise 3: is this tree symmetric?
Root 1. Its left child is 2 with a child 3 on the left. Its right child is 2 with a child 3 on the left as well.
Show the answer
No. The two 3s are on the same side, so they do not face each other across the root. The check isSymmetric returns false. The same-direction check isSymmetricWrong returns true, which is the wrong answer here.
Exercise 4: why does a single leaf work?
Explain what invert does when it is called on a leaf that holds the value 7.
Show the answer
A leaf has no children. The function swaps two empty pointers, which changes nothing. Then it calls invert on each empty child, and each of those calls returns at the first line. The output is still 7 . ., which is the leaf with two dots for its missing children.
Exercise 5: why recurse after the swap?
In invert, the swap happens before the two recursive calls. Explain whether the result changes if the recursive calls come first, before the swap.
Show the answer
The result is the same. If the two calls run first, each child subtree is inverted where it sits. Then the swap moves the finished subtrees to the other side. Each node is still inverted exactly once, so the final tree is the same mirror image. The swap-first order is easier to read, which is why it is the usual style.
Summary
- Inverting a tree swaps the left and right child of every node, which makes its mirror image in place.
- Two trees are mirrors when their roots match, the left of one matches the right of the other, and the right of one matches the left of the other.
- A tree is symmetric when its left child and right child are mirrors of each other.
- A missing child matches only a missing child, so the base case returns
a == bfor empty pointers. - The queue version does the same check with pairs of nodes and uses no recursion.