The challenge
Check whether the tree is a mirror of itself in both values and shape.
Null positions matter. An empty tree is symmetric.
Example
The first example is symmetric; the sparse example has equal values but mismatched child positions.
Use the walkthrough below to inspect the input and each state change.
See Symmetry, step by step
Follow the branches. Watch the state change.
View child pointers & node state
| Node | Value | Left | Right | State |
|---|---|---|---|---|
| A | 1 | B | C | — |
| B | 2 | D | E | — |
| C | 2 | F | G | — |
| D | 3 | null | null | — |
| E | 4 | null | null | — |
| F | 4 | null | null | — |
| G | 3 | null | null | — |
Inspect the input.
Labels identify node objects; numbers are their values. Left and right child pointers define the tree.
root = A:1View original input
A:1 [L:B, R:C] · B:2 [L:D, R:E] · C:2 [L:F, R:G] · D:3 [L:null, R:null] · E:4 [L:null, R:null] · F:4 [L:null, R:null] · G:3 [L:null, R:null]
Node IDs stay distinct even when values repeat. Pointer mutations update the diagram; removed nodes remain in the state table for reference.
Put it into code
Compare pairs of positions reflected across the root.
Nodes store value, left, and right. C++ uses C++17 or later.
from collections import deque
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def is_symmetric(root):
def mirror(a, b):
if a is None or b is None:
return a is b
return (a.value == b.value
and mirror(a.left, b.right)
and mirror(a.right, b.left))
return root is None or mirror(root.left, root.right)
#include <algorithm>
#include <cmath>
#include <functional>
#include <limits>
#include <map>
#include <optional>
#include <queue>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
struct Node {
long long value;
Node *left = nullptr, *right = nullptr;
explicit Node(long long v) : value(v) {}
};
bool is_symmetric(Node* root) {
function<bool(Node*, Node*)> mirror = [&](Node* a, Node* b) {
if (!a || !b) return a == b;
return a->value == b->value
&& mirror(a->left, b->right)
&& mirror(a->right, b->left);
};
return !root || mirror(root->left, root->right);
}