DSA Tracker

Visualize

Isomorphic Trees

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

time O(min(4^h, 2^n))space O(h) recursion stack

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.

Details

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.

Problem:Isomorphic TreesMedium

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

step 1 / 11

4
2
5
1
=
3
2
1
=
5
3
4
T1|T2

Call stack

iso(1, 1)

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

Every step in words

Show all 11 steps
  1. 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).
  2. Values match at (2, 2). That alone proves nothing — try the STRAIGHT pairing (left↔left, right↔right) first, then the SWAPPED pairing (left↔right, right↔left).
  3. One side is null while the other holds 4: the shapes disagree here, so this pairing is false immediately — no swap fixes a missing node.
  4. Straight pairing at (2, 2) failed — AND short-circuits, so the second call was skipped. Now try the swapped pairing.
  5. One side is null while the other holds 4: the shapes disagree here, so this pairing is false immediately — no swap fixes a missing node.
  6. Swapped pairing at (2, 2) also failed — AND short-circuits again, skipping whatever was left.
  7. Neither configuration worked at (2, 2), so iso(2, 2) resolves to false and pops.
  8. Straight pairing at (1, 1) failed — AND short-circuits, so the second call was skipped. Now try the swapped pairing.
  9. Values differ (2 vs 3): swapping only reorders children, it never changes a node's own value, so this pairing is false immediately.
  10. Swapped pairing at (1, 1) also failed — AND short-circuits again, skipping whatever was left.
  11. Neither configuration worked at (1, 1), so iso(1, 1) resolves to false and pops.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Isomorphic Trees in the editorAll Binary Trees problemsBack to roadmap