DSA Symmetric Tree
A binary tree is symmetric when its left subtree is the mirror image of its right subtree, in values and in shape at once. The check pairs nodes across the middle instead of comparing values level by level.
The problem
A binary tree is symmetric when its left half is the mirror image of its right half. Mirror image means two things at once. Values in mirrored positions match. The shape in mirrored positions also matches.
The answer is a single yes or no. The code below builds four trees and prints each one in level order. Level order lists nodes row by row, with None for a missing child. The expected verdict sits beside each tree.
The cases used in this article
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def level_order(root):
if root is None:
return []
out = []
queue = [root]
while queue:
node = queue.pop(0)
if node is None:
out.append(None)
else:
out.append(node.value)
queue.append(node.left)
queue.append(node.right)
while out and out[-1] is None:
out.pop()
return out
full = TreeNode(1, TreeNode(2, TreeNode(3), TreeNode(4)), TreeNode(2, TreeNode(4), TreeNode(3)))
bent = TreeNode(1, TreeNode(2, None, TreeNode(3)), TreeNode(2, None, TreeNode(3)))
wrong_value = TreeNode(1, TreeNode(2, TreeNode(3), TreeNode(4)), TreeNode(2, TreeNode(4), TreeNode(5)))
print("full:", level_order(full), "expected True")
print("bent:", level_order(bent), "expected False")
print("wrong value:", level_order(wrong_value), "expected False")
print("single node:", level_order(TreeNode(1)), "expected True")
print("empty tree:", level_order(None), "expected True")The full tree mirrors perfectly. The 3 and the 4 trade places across the middle. The bent tree holds the same values on both sides, but both 3s lean the same way. That bend is enough to fail.
Intuition
The first idea is to compare values level by level. Each row reads the same from the left and from the right, so the tree looks symmetric. That test checks values only. It never checks where the empty slots sit.
The bent tree passes that test. Each of its rows holds the same values on the left and on the right. Its shape still fails, because a 3 sits against an empty slot in the mirrored pairing.
Level values pass, the mirror fails
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def level_order(root):
if root is None:
return []
out = []
queue = [root]
while queue:
node = queue.pop(0)
if node is None:
out.append(None)
else:
out.append(node.value)
queue.append(node.left)
queue.append(node.right)
while out and out[-1] is None:
out.pop()
return out
def level_values_ok(root):
if root is None:
return True
level = [root]
while level:
vals = [n.value for n in level if n is not None]
if vals != vals[::-1]:
return False
nxt = []
for n in level:
if n is not None:
nxt.append(n.left)
nxt.append(n.right)
level = [n for n in nxt if n is not None]
return True
def is_mirror(a, b):
if a is None and b is None:
return True
if a is None or b is None:
return False
if a.value != b.value:
return False
return is_mirror(a.left, b.right) and is_mirror(a.right, b.left)
bent = TreeNode(1, TreeNode(2, None, TreeNode(3)), TreeNode(2, None, TreeNode(3)))
print("level values check:", level_values_ok(bent))
print("mirror check:", is_mirror(bent.left, bent.right))The two checks disagree on the same tree. Values alone cannot see structure. A correct check has to pair a node on one side with a node on the other side and compare the pair in place.
Brute force
A direct route builds the mirror and then compares. Mirror the right subtree by swapping its children at every node. Then walk the left subtree and the mirrored copy together and demand equal values and equal shapes.
The route works. It is clumsy in two ways. It builds a whole second tree, and it visits nodes twice, once to copy and once to compare.
Mirror a copy, then compare
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def level_order(root):
if root is None:
return []
out = []
queue = [root]
while queue:
node = queue.pop(0)
if node is None:
out.append(None)
else:
out.append(node.value)
queue.append(node.left)
queue.append(node.right)
while out and out[-1] is None:
out.pop()
return out
copied = 0
compared = 0
def mirror_copy(node):
global copied
if node is None:
return None
copied += 1
return TreeNode(node.value, mirror_copy(node.right), mirror_copy(node.left))
def same(a, b):
global compared
if a is None and b is None:
return True
if a is None or b is None:
return False
compared += 1
return a.value == b.value and same(a.left, b.left) and same(a.right, b.right)
def brute(root):
global copied, compared
copied = 0
compared = 0
if root is None:
return True
return same(root.left, mirror_copy(root.right))
full = TreeNode(1, TreeNode(2, TreeNode(3), TreeNode(4)), TreeNode(2, TreeNode(4), TreeNode(3)))
bent = TreeNode(1, TreeNode(2, None, TreeNode(3)), TreeNode(2, None, TreeNode(3)))
print("full:", brute(full), "copied:", copied, "compared:", compared)
print("bent:", brute(bent), "copied:", copied, "compared:", compared)Both verdicts are right. The counters show the extra work. The optimal check needs no copy at all, because it pairs nodes from the two original subtrees directly.
The optimal solution: pair the two sides
The key idea is one sentence. Two subtrees mirror each other when their roots match and the outer children mirror each other and the inner children mirror each other.
Outer means left against right. Inner also means right against left. That crossed pairing is the whole mirror idea in code.
The mirror-pair solution, run on every case
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def level_order(root):
if root is None:
return []
out = []
queue = [root]
while queue:
node = queue.pop(0)
if node is None:
out.append(None)
else:
out.append(node.value)
queue.append(node.left)
queue.append(node.right)
while out and out[-1] is None:
out.pop()
return out
def is_mirror(a, b):
if a is None and b is None:
return True
if a is None or b is None:
return False
if a.value != b.value:
return False
return is_mirror(a.left, b.right) and is_mirror(a.right, b.left)
def is_symmetric(root):
if root is None:
return True
return is_mirror(root.left, root.right)
full = TreeNode(1, TreeNode(2, TreeNode(3), TreeNode(4)), TreeNode(2, TreeNode(4), TreeNode(3)))
bent = TreeNode(1, TreeNode(2, None, TreeNode(3)), TreeNode(2, None, TreeNode(3)))
wrong_value = TreeNode(1, TreeNode(2, TreeNode(3), TreeNode(4)), TreeNode(2, TreeNode(4), TreeNode(5)))
print("full:", is_symmetric(full))
print("bent:", is_symmetric(bent))
print("wrong value:", is_symmetric(wrong_value))
print("single node:", is_symmetric(TreeNode(1)))
print("empty tree:", is_symmetric(None))All five cases from the first section pass. No copy was built. Each pair of nodes is compared where it stands.
Walkthrough
Take the full tree from the first section. Its root is 1. The check starts with the pair below the root, the two 2s.
The trace prints each pair as it is checked. Outer pairs come before inner pairs at each step. That order follows the code exactly.
Tracing the pairs on the full tree
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def level_order(root):
if root is None:
return []
out = []
queue = [root]
while queue:
node = queue.pop(0)
if node is None:
out.append(None)
else:
out.append(node.value)
queue.append(node.left)
queue.append(node.right)
while out and out[-1] is None:
out.pop()
return out
def is_mirror(a, b, depth=0):
def name(n):
return "None" if n is None else str(n.value)
print(" " * depth + "pair", name(a), "vs", name(b))
if a is None and b is None:
return True
if a is None or b is None:
return False
if a.value != b.value:
return False
return is_mirror(a.left, b.right, depth + 1) and is_mirror(a.right, b.left, depth + 1)
full = TreeNode(1, TreeNode(2, TreeNode(3), TreeNode(4)), TreeNode(2, TreeNode(4), TreeNode(3)))
print("verdict:", is_mirror(full.left, full.right))The first pair matches on value 2. Its outer children are 3 and 3, which also match. Its inner children are 4 and 4, which match as well. The empty pairs below the leaves match too, so every pair passes and the verdict is True.
Complexity
Time is O(n) for a tree of n nodes. Each node takes part in one pair check, so the pair count grows with the tree.
Space is O(h) for a tree of height h. The extra memory is the call stack, one frame per level on the current path. No second tree is stored.
Counting pair checks as trees grow
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def level_order(root):
if root is None:
return []
out = []
queue = [root]
while queue:
node = queue.pop(0)
if node is None:
out.append(None)
else:
out.append(node.value)
queue.append(node.left)
queue.append(node.right)
while out and out[-1] is None:
out.pop()
return out
checks = 0
def is_mirror(a, b):
global checks
checks += 1
if a is None and b is None:
return True
if a is None or b is None:
return False
if a.value != b.value:
return False
return is_mirror(a.left, b.right) and is_mirror(a.right, b.left)
def build(depth, value=1):
if depth == 0:
return None
return TreeNode(value, build(depth - 1), build(depth - 1))
for depth in [2, 3, 4]:
tree = build(depth)
checks = 0
is_mirror(tree.left, tree.right)
nodes = 2 ** depth - 1
print("depth", depth, "nodes:", nodes, "pair checks:", checks)The pair count tracks the node count. Double the nodes and the checks roughly double. That straight line is the O(n) claim made visible.
Edge cases and pitfalls
An empty tree is symmetric. It has no pair that could disagree. A single node is symmetric for the same reason.
A root with only one child is never symmetric. One side of the first pair is a node and the other side is empty, so that pair fails at once. Equal values do not rescue a missing node, and equal shapes do not rescue a wrong value.
Edge cases, run
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def level_order(root):
if root is None:
return []
out = []
queue = [root]
while queue:
node = queue.pop(0)
if node is None:
out.append(None)
else:
out.append(node.value)
queue.append(node.left)
queue.append(node.right)
while out and out[-1] is None:
out.pop()
return out
def is_mirror(a, b):
if a is None and b is None:
return True
if a is None or b is None:
return False
if a.value != b.value:
return False
return is_mirror(a.left, b.right) and is_mirror(a.right, b.left)
def is_symmetric(root):
if root is None:
return True
return is_mirror(root.left, root.right)
print("empty:", is_symmetric(None))
print("single:", is_symmetric(TreeNode(7)))
print("left child only:", is_symmetric(TreeNode(1, TreeNode(2))))
print("both children, equal:", is_symmetric(TreeNode(1, TreeNode(2), TreeNode(2))))
print("both children, unequal:", is_symmetric(TreeNode(1, TreeNode(2), TreeNode(3))))
print("inner pair holds the 3s:", is_symmetric(TreeNode(1, TreeNode(2, None, TreeNode(3)), TreeNode(2, TreeNode(3)))))The last tree is the exercise shape. Its two 3s sit in the inner positions, the right child of the left 2 and the left child of the right 2. Inner pairs are checked crossed, so that tree passes.
Exercise
A tree has root 1, left child 2 and right child 2. The left 2 has a right child 3, and the right 2 has a left child 3. Is the tree symmetric?