24.07Intermediate / Advanced5 topics17 min5 interactive animations

Tree transformation

Changing and rebuilding trees: inverting, flattening, building from preorder or postorder plus inorder, and serialising and deserialising.

Learning goals

Mirror a tree and flatten it in place
Rebuild a tree from preorder or postorder plus inorder
Explain why inorder is needed and what one traversal alone cannot tell
Serialise a tree to text and read it back

Prerequisites

Traversal methodsBinary tree representation

Rewiring pointers, reconstructing a tree from its traversals and saving it to text are the standard exercises in thinking about trees as recursive structures.

24.07.1

Invert tree

**Inverting** (mirroring) a tree swaps the left and right child of every node. Recurse into both subtrees, or swap first and then recurse; either order works, since each node's swap is independent. The “Invert” preset swaps 7 nodes once each, so the cost is O(n).

Use postorder if the code reads the children after inverting them, and be careful not to lose a pointer: save one child in a temporary before overwriting it.

Java

1static TreeNode invert(TreeNode n) {
2    if (n == null) return null;
3    TreeNode left = invert(n.left), right = invert(n.right);
4    n.left = right;                                  // swap the two subtrees
5    n.right = left;
6    return n;
7}

Best

O(n)

Average

O(n)

Worst

O(n)

Space

O(h)

Transforming trees: invert, flatten, serialize and deserialize

Interactive · edit the input

binary tree · 6 nodes

Current nodeChildren swappedFinishedJust createdRewired

Setup

Inverting swaps every node's two children. Do it after both subtrees are inverted, or before: either order works.

Step 1 / 8

Java

1static TreeNode invert(TreeNode n) {
2    if (n == null) return null;
3    TreeNode left = invert(n.left), right = invert(n.right);
4    n.left = right; n.right = left;              // swap the two subtrees
5    return n;
6}
7static void flatten(TreeNode root) {             // in place: a right-leaning chain in preorder
8    for (TreeNode cur = root; cur != null; cur = cur.right) {
9        if (cur.left == null) continue;
10        TreeNode last = cur.left;
11        while (last.right != null) last = last.right;   // rightmost node of the left subtree
12        last.right = cur.right;                  // the old right subtree hangs below it
13        cur.right = cur.left;
14        cur.left = null;
15    }
16}
17static String serialize(TreeNode n) {
18    if (n == null) return "#";
19    return n.val + " " + serialize(n.left) + " " + serialize(n.right);   // preorder, # for empty
20}
21static TreeNode deserialize(Iterator<String> tokens) {
22    String t = tokens.next();
23    if (t.equals("#")) return null;
24    TreeNode n = new TreeNode(Integer.parseInt(t));
25    n.left = deserialize(tokens);
26    n.right = deserialize(tokens);
27    return n;
28}

Live state

swaps

No condition evaluated on this step

Execution trace (dry run table)Show 8 steps

Step	Line	State	What happens
1	L1	swaps=0	Inverting swaps every node's two children. Do it after both subtrees are inverted, or before: either order works.
2	L4	swaps=1	Swap the children of 3 (a leaf: nothing to swap, both are empty).
3	L4	swaps=2	Swap the children of 4 (a leaf: nothing to swap, both are empty).
4	L4	swaps=3	Swap the children of 2: its left child is now 4 and its right child is 3.
5	L4	swaps=4	Swap the children of 6 (a leaf: nothing to swap, both are empty).
6	L4	swaps=5	Swap the children of 5: its left child is now 6 and its right child is empty.
7	L4	swaps=6	Swap the children of 1: its left child is now 5 and its right child is 2.
8	L5	swaps=6	The tree is mirrored. 6 nodes were visited once each, so the cost is O(n).

24.07.2

Flatten tree

**Flattening** rewires a tree in place into a right-leaning chain in preorder, with every left pointer null. For each node that has a left child, find the rightmost node of the left subtree, hang the node's old right subtree below it, then make the left subtree the new right child. Continue along the right pointer. Each node is touched a constant number of times plus the rightmost searches, which total O(n).

The “Flatten” preset turns “1 2 5 3 4 # 6” into the chain 1 → 2 → 3 → 4 → 5 → 6, the original preorder.

Java

1static void flatten(TreeNode root) {
2    for (TreeNode cur = root; cur != null; cur = cur.right) {
3        if (cur.left == null) continue;
4        TreeNode last = cur.left;
5        while (last.right != null) last = last.right;    // rightmost node of the left subtree
6        last.right = cur.right;                          // the old right subtree hangs below it
7        cur.right = cur.left;
8        cur.left = null;
9    }
10}

Best

O(n)

Average

O(n)

Worst

O(n)

Space

O(1)

Transforming trees: invert, flatten, serialize and deserialize

Interactive · edit the input

binary tree · 6 nodes

Current nodeChildren swappedFinishedJust createdRewired

Setup

Inverting swaps every node's two children. Do it after both subtrees are inverted, or before: either order works.

Step 1 / 8

Java

1static TreeNode invert(TreeNode n) {
2    if (n == null) return null;
3    TreeNode left = invert(n.left), right = invert(n.right);
4    n.left = right; n.right = left;              // swap the two subtrees
5    return n;
6}
7static void flatten(TreeNode root) {             // in place: a right-leaning chain in preorder
8    for (TreeNode cur = root; cur != null; cur = cur.right) {
9        if (cur.left == null) continue;
10        TreeNode last = cur.left;
11        while (last.right != null) last = last.right;   // rightmost node of the left subtree
12        last.right = cur.right;                  // the old right subtree hangs below it
13        cur.right = cur.left;
14        cur.left = null;
15    }
16}
17static String serialize(TreeNode n) {
18    if (n == null) return "#";
19    return n.val + " " + serialize(n.left) + " " + serialize(n.right);   // preorder, # for empty
20}
21static TreeNode deserialize(Iterator<String> tokens) {
22    String t = tokens.next();
23    if (t.equals("#")) return null;
24    TreeNode n = new TreeNode(Integer.parseInt(t));
25    n.left = deserialize(tokens);
26    n.right = deserialize(tokens);
27    return n;
28}

Live state

swaps

No condition evaluated on this step

Execution trace (dry run table)Show 8 steps

Step	Line	State	What happens
1	L1	swaps=0	Inverting swaps every node's two children. Do it after both subtrees are inverted, or before: either order works.
2	L4	swaps=1	Swap the children of 3 (a leaf: nothing to swap, both are empty).
3	L4	swaps=2	Swap the children of 4 (a leaf: nothing to swap, both are empty).
4	L4	swaps=3	Swap the children of 2: its left child is now 4 and its right child is 3.
5	L4	swaps=4	Swap the children of 6 (a leaf: nothing to swap, both are empty).
6	L4	swaps=5	Swap the children of 5: its left child is now 6 and its right child is empty.
7	L4	swaps=6	Swap the children of 1: its left child is now 5 and its right child is 2.
8	L5	swaps=6	The tree is mirrored. 6 nodes were visited once each, so the cost is O(n).

24.07.3

Build from preorder+inorder

Preorder alone does not identify a tree (many trees share one preorder), and neither does inorder alone, but **together** they do, provided the values are distinct. The first preorder value is the root. Its position in the inorder sequence splits the other values: those before it form the left subtree, those after it the right. Recurse with the next preorder values, consuming them in order. A hash map from value to inorder index makes each split O(1), so the whole build is O(n).

The “Preorder + inorder” preset rebuilds the tree with root 3 from preorder “3 9 20 15 7” and inorder “9 3 15 20 7”: 9 is left of 3, and 15, 20, 7 are right of it. The animation highlights the inorder segment being split.

Java

1static TreeNode buildPreIn(int[] pre, int[] in) {
2    Map<Integer, Integer> at = new HashMap<>();
3    for (int i = 0; i < in.length; i++) at.put(in[i], i);
4    return buildPre(pre, at, new int[]{0}, 0, in.length - 1);
5}
6static TreeNode buildPre(int[] pre, Map<Integer, Integer> at, int[] next, int lo, int hi) {
7    if (lo > hi) return null;
8    TreeNode root = new TreeNode(pre[next[0]++]);        // the next preorder value is this subtree's root
9    int mid = at.get(root.val);                          // its inorder position splits left from right
10    root.left = buildPre(pre, at, next, lo, mid - 1);
11    root.right = buildPre(pre, at, next, mid + 1, hi);   // left first: preorder lists the left subtree first
12    return root;
13}

Best

O(n)

Average

O(n)

Worst

O(n)

Space

O(n)

Rebuilding a binary tree from preorder or postorder plus inorder

Interactive · edit the input

preorder (root first)

inorder (left subtree, root, right subtree)

Setup

Preorder lists a root before its subtrees, so its first value is the root. Inorder shows which values are on its left and right.

Step 1 / 13

Java

1static TreeNode buildPreIn(int[] pre, int[] in) {
2    Map<Integer, Integer> at = new HashMap<>();
3    for (int i = 0; i < in.length; i++) at.put(in[i], i);
4    return buildPre(pre, at, new int[]{0}, 0, in.length - 1);
5}
6static TreeNode buildPre(int[] pre, Map<Integer, Integer> at, int[] next, int lo, int hi) {
7    if (lo > hi) return null;
8    TreeNode root = new TreeNode(pre[next[0]++]);   // the next preorder value is this subtree's root
9    int mid = at.get(root.val);                     // its inorder position splits left from right
10    root.left = buildPre(pre, at, next, lo, mid - 1);
11    root.right = buildPre(pre, at, next, mid + 1, hi);
12    return root;
13}
14static TreeNode buildPostIn(int[] post, int[] in) {
15    Map<Integer, Integer> at = new HashMap<>();
16    for (int i = 0; i < in.length; i++) at.put(in[i], i);
17    return buildPost(post, at, new int[]{post.length - 1}, 0, in.length - 1);
18}
19static TreeNode buildPost(int[] post, Map<Integer, Integer> at, int[] next, int lo, int hi) {
20    if (lo > hi) return null;
21    TreeNode root = new TreeNode(post[next[0]--]); // the last postorder value is the root
22    int mid = at.get(root.val);
23    root.right = buildPost(post, at, next, mid + 1, hi);   // right subtree first: postorder ends with it
24    root.left = buildPost(post, at, next, lo, mid - 1);
25    return root;
26}

Live state

0 nodes built

segment

[0, 4]

No condition evaluated on this step

Execution trace (dry run table)Show 13 steps

Step	Line	State	What happens
1	L1	segment=[0, 4]	Preorder lists a root before its subtrees, so its first value is the root. Inorder shows which values are on its left and right.
2	L8	root=3 inorder position=1 segment=[0, 4]	Segment [0, 4]: the next preorder value is 3. It sits at inorder position 1, so 1 value go left and 3 go right.
3	L8	root=9 inorder position=0 segment=[0, 0]	Segment [0, 0]: the next preorder value is 9. It sits at inorder position 0, so 0 values go left and 0 go right.
4	L7	segment=[0, -1]	The segment [0, -1] is empty: this child is null.
5	L7	segment=[1, 0]	The segment [1, 0] is empty: this child is null.
6	L8	root=20 inorder position=3 segment=[2, 4]	Segment [2, 4]: the next preorder value is 20. It sits at inorder position 3, so 1 value go left and 1 go right.
7	L8	root=15 inorder position=2 segment=[2, 2]	Segment [2, 2]: the next preorder value is 15. It sits at inorder position 2, so 0 values go left and 0 go right.
8	L7	segment=[2, 1]	The segment [2, 1] is empty: this child is null.
9	L7	segment=[3, 2]	The segment [3, 2] is empty: this child is null.
10	L8	root=7 inorder position=4 segment=[4, 4]	Segment [4, 4]: the next preorder value is 7. It sits at inorder position 4, so 0 values go left and 0 go right.
11	L7	segment=[4, 3]	The segment [4, 3] is empty: this child is null.
12	L7	segment=[5, 4]	The segment [5, 4] is empty: this child is null.
13	L12	nodes=5	The tree is rebuilt with 5 nodes. The inorder order is what tells left from right; with preorder or postorder alone, many trees fit.

24.07.4

Build from postorder+inorder

Postorder lists the root **last**, so the roles flip: take the root from the end of the postorder list. Because the sequence is read backwards, the nodes consumed after the root belong to the **right** subtree first, then the left. Build the right subtree before the left, or the values come out in the wrong places.

The “Postorder + inorder” preset uses postorder “9 15 7 20 3” with the same inorder as before. The “Right chain (postorder)” preset with postorder “3 2 1” and inorder “1 2 3” gives a right-leaning chain: root 1, its right child 2, and 2's right child 3.

Preorder with postorder, without inorder, is not enough: for a node with a single child you cannot tell whether it is the left or the right child.

Java

1static TreeNode buildPostIn(int[] post, int[] in) {
2    Map<Integer, Integer> at = new HashMap<>();
3    for (int i = 0; i < in.length; i++) at.put(in[i], i);
4    return buildPost(post, at, new int[]{post.length - 1}, 0, in.length - 1);
5}
6static TreeNode buildPost(int[] post, Map<Integer, Integer> at, int[] next, int lo, int hi) {
7    if (lo > hi) return null;
8    TreeNode root = new TreeNode(post[next[0]--]);       // the last postorder value is the root
9    int mid = at.get(root.val);
10    root.right = buildPost(post, at, next, mid + 1, hi); // right subtree first: it is read first from the end
11    root.left = buildPost(post, at, next, lo, mid - 1);
12    return root;
13}

Best

O(n)

Average

O(n)

Worst

O(n)

Space

O(n)

Rebuilding a binary tree from preorder or postorder plus inorder

Interactive · edit the input

preorder (root first)

inorder (left subtree, root, right subtree)

Setup

Preorder lists a root before its subtrees, so its first value is the root. Inorder shows which values are on its left and right.

Step 1 / 13

Java

1static TreeNode buildPreIn(int[] pre, int[] in) {
2    Map<Integer, Integer> at = new HashMap<>();
3    for (int i = 0; i < in.length; i++) at.put(in[i], i);
4    return buildPre(pre, at, new int[]{0}, 0, in.length - 1);
5}
6static TreeNode buildPre(int[] pre, Map<Integer, Integer> at, int[] next, int lo, int hi) {
7    if (lo > hi) return null;
8    TreeNode root = new TreeNode(pre[next[0]++]);   // the next preorder value is this subtree's root
9    int mid = at.get(root.val);                     // its inorder position splits left from right
10    root.left = buildPre(pre, at, next, lo, mid - 1);
11    root.right = buildPre(pre, at, next, mid + 1, hi);
12    return root;
13}
14static TreeNode buildPostIn(int[] post, int[] in) {
15    Map<Integer, Integer> at = new HashMap<>();
16    for (int i = 0; i < in.length; i++) at.put(in[i], i);
17    return buildPost(post, at, new int[]{post.length - 1}, 0, in.length - 1);
18}
19static TreeNode buildPost(int[] post, Map<Integer, Integer> at, int[] next, int lo, int hi) {
20    if (lo > hi) return null;
21    TreeNode root = new TreeNode(post[next[0]--]); // the last postorder value is the root
22    int mid = at.get(root.val);
23    root.right = buildPost(post, at, next, mid + 1, hi);   // right subtree first: postorder ends with it
24    root.left = buildPost(post, at, next, lo, mid - 1);
25    return root;
26}

Live state

0 nodes built

segment

[0, 4]

No condition evaluated on this step

Execution trace (dry run table)Show 13 steps

Step	Line	State	What happens
1	L1	segment=[0, 4]	Preorder lists a root before its subtrees, so its first value is the root. Inorder shows which values are on its left and right.
2	L8	root=3 inorder position=1 segment=[0, 4]	Segment [0, 4]: the next preorder value is 3. It sits at inorder position 1, so 1 value go left and 3 go right.
3	L8	root=9 inorder position=0 segment=[0, 0]	Segment [0, 0]: the next preorder value is 9. It sits at inorder position 0, so 0 values go left and 0 go right.
4	L7	segment=[0, -1]	The segment [0, -1] is empty: this child is null.
5	L7	segment=[1, 0]	The segment [1, 0] is empty: this child is null.
6	L8	root=20 inorder position=3 segment=[2, 4]	Segment [2, 4]: the next preorder value is 20. It sits at inorder position 3, so 1 value go left and 1 go right.
7	L8	root=15 inorder position=2 segment=[2, 2]	Segment [2, 2]: the next preorder value is 15. It sits at inorder position 2, so 0 values go left and 0 go right.
8	L7	segment=[2, 1]	The segment [2, 1] is empty: this child is null.
9	L7	segment=[3, 2]	The segment [3, 2] is empty: this child is null.
10	L8	root=7 inorder position=4 segment=[4, 4]	Segment [4, 4]: the next preorder value is 7. It sits at inorder position 4, so 0 values go left and 0 go right.
11	L7	segment=[4, 3]	The segment [4, 3] is empty: this child is null.
12	L7	segment=[5, 4]	The segment [5, 4] is empty: this child is null.
13	L12	nodes=5	The tree is rebuilt with 5 nodes. The inorder order is what tells left from right; with preorder or postorder alone, many trees fit.

24.07.5

Serialize/deserialize

To save a tree to text and read it back, write it in preorder and mark every empty child with a token such as #. The shape is then fully determined: reading tokens in the same order, a number creates a node followed by its left and right subtrees, and # returns null. A tree with n nodes has n + 1 empty children, so the serialised text has 2n + 1 tokens: the 5-node preset gives 11.

The animation shows both halves: the tokens appended during serialisation, and the rebuilt tree growing as tokens are consumed. Level-order serialisation (the format of the input boxes in this course) works too, with a queue; preorder is shorter to write recursively.

Java

1static String serialize(TreeNode n) {
2    if (n == null) return "#";
3    return n.val + " " + serialize(n.left) + " " + serialize(n.right);   // preorder, # for empty
4}
5static TreeNode deserialize(String data) {
6    return read(new ArrayDeque<>(Arrays.asList(data.split(" "))));
7}
8static TreeNode read(Deque<String> tokens) {
9    String t = tokens.poll();
10    if (t.equals("#")) return null;
11    TreeNode n = new TreeNode(Integer.parseInt(t));
12    n.left = read(tokens);
13    n.right = read(tokens);
14    return n;
15}

Best

O(n)

Average

O(n)

Worst

O(n)

Space

O(n)

Transforming trees: invert, flatten, serialize and deserialize

Interactive · edit the input

binary tree · 6 nodes

Current nodeChildren swappedFinishedJust createdRewired

Setup

Inverting swaps every node's two children. Do it after both subtrees are inverted, or before: either order works.

Step 1 / 8

Java

1static TreeNode invert(TreeNode n) {
2    if (n == null) return null;
3    TreeNode left = invert(n.left), right = invert(n.right);
4    n.left = right; n.right = left;              // swap the two subtrees
5    return n;
6}
7static void flatten(TreeNode root) {             // in place: a right-leaning chain in preorder
8    for (TreeNode cur = root; cur != null; cur = cur.right) {
9        if (cur.left == null) continue;
10        TreeNode last = cur.left;
11        while (last.right != null) last = last.right;   // rightmost node of the left subtree
12        last.right = cur.right;                  // the old right subtree hangs below it
13        cur.right = cur.left;
14        cur.left = null;
15    }
16}
17static String serialize(TreeNode n) {
18    if (n == null) return "#";
19    return n.val + " " + serialize(n.left) + " " + serialize(n.right);   // preorder, # for empty
20}
21static TreeNode deserialize(Iterator<String> tokens) {
22    String t = tokens.next();
23    if (t.equals("#")) return null;
24    TreeNode n = new TreeNode(Integer.parseInt(t));
25    n.left = deserialize(tokens);
26    n.right = deserialize(tokens);
27    return n;
28}

Live state

swaps

No condition evaluated on this step

Execution trace (dry run table)Show 8 steps

Step	Line	State	What happens
1	L1	swaps=0	Inverting swaps every node's two children. Do it after both subtrees are inverted, or before: either order works.
2	L4	swaps=1	Swap the children of 3 (a leaf: nothing to swap, both are empty).
3	L4	swaps=2	Swap the children of 4 (a leaf: nothing to swap, both are empty).
4	L4	swaps=3	Swap the children of 2: its left child is now 4 and its right child is 3.
5	L4	swaps=4	Swap the children of 6 (a leaf: nothing to swap, both are empty).
6	L4	swaps=5	Swap the children of 5: its left child is now 6 and its right child is empty.
7	L4	swaps=6	Swap the children of 1: its left child is now 5 and its right child is 2.
8	L5	swaps=6	The tree is mirrored. 6 nodes were visited once each, so the cost is O(n).

Practice ladder

Now try it yourself

Easy

Invert Binary Tree
Symmetric Tree

Medium

Flatten Binary Tree to Linked List
Construct Binary Tree from Preorder and Inorder Traversal
Construct Binary Tree from Inorder and Postorder Traversal

Advanced

Serialize and Deserialize Binary Tree
Construct Binary Tree from Preorder and Postorder Traversal

Key takeaways

Inverting swaps the children of every node, in O(n).
Flatten rewires the tree in place into the preorder chain.
Inorder plus preorder or postorder (distinct values) fixes a tree; the root comes from the front of preorder or the back of postorder.
Postorder reconstruction builds the right subtree first.
Preorder with # markers serialises a tree in 2n + 1 tokens.