Pattern visualizer

Check if Tree is Isomorphic

Two trees are isomorphic if, at every node, either their children already correspond straight across, or they correspond once one side's children are swapped. So at each pair of nodes there are two configurations to test: (left↔left, right↔right) or (left↔right, right↔left). A null paired with a real node is an immediate mismatch — no swap can invent or delete a node — and a value mismatch is immediate too, since swapping only reorders children, never changes a node's own value. Animated on: root1 = [1,2,3,4,5], root2 = [1,2,3,null,null,5,4] — are the two trees isomorphic (one obtainable from the other by swapping the left and right children of some nodes)? Expected: false..

At every node, try the straight pairing, then the swapped pairing

time O(min(4^h, 2^n))space O(h) recursion stackstep 1 / 11

T1|T2

Call stack

iso(1, 1)

line 8

Values match at (1, 1). That alone proves nothing — try the STRAIGHT pairing (left↔left, right↔right) first, then the SWAPPED pairing (left↔right, right↔left).

Pseudocode

1FUNCTION isIso(a, b):
2  IF a = null AND b = null:
3    RETURN true
4  IF a = null OR b = null:
5    RETURN false
6  IF a.val != b.val:
7    RETURN false
8  straight <- isIso(a.left, b.left) AND isIso(a.right, b.right)
9  swapped <- isIso(a.left, b.right) AND isIso(a.right, b.left)
10  RETURN straight OR swapped

← / → step · space play · Home restart

Where to practice Binary Trees

Practice Binary Trees problems All Binary Trees problems Back to roadmap