Construction & Serialization

Flatten to Linked List

Convert a binary tree to a 'linked list' using only right pointers, in pre-order. For each node: save the right child, point right to the left child, find the rightmost node of the left subtree, connect it to the saved right child.

O(n)

O(1)

How It Works

Flattening rearranges a binary tree into a right-leaning chain whose node order matches pre-order traversal, in place. The elegant iterative method processes one node at a time: if the current node has a left child, find that left subtree's rightmost node (its pre-order tail), wire that node's right pointer to the current right subtree, move the left subtree into the right slot, and null the left pointer. Then step right and repeat.

This is essentially Morris-style rewiring, and the same amortized argument applies: each node's rightmost-descent is walked a bounded number of times, so total time is O(n) with O(1) extra space. A recursive alternative flattens in reverse pre-order (right, left, root), maintaining a "previously flattened head" pointer that each node hooks onto — simpler to reason about but O(h) stack. Either way, no new nodes are allocated; only pointers move.

Step-by-Step Visualization

Flatten tree to linked list (pre-order)

Goal1→2→3→4→5→6

1/3

Code

Java

static TreeNode prev = null;

static void flatten(TreeNode root) {
  prev = null;
  dfs(root);
}

static void dfs(TreeNode node) {
  if (node == null) return;
  dfs(node.right);
  dfs(node.left);
  node.right = prev;
  node.left = null;
  prev = node;
}

// Tree [1,2,5,3,4,null,6] → 1→2→3→4→5→6

Tips & Gotchas

1Process in reverse post-order: right, left, root

2Each node's right points to the previously processed node

3Or use Morris-style: connect left subtree's rightmost to right child

Practice Problems

1Flatten Binary Tree to Linked List
2Convert Binary Search Tree to Sorted Doubly Linked List
3Increasing Order Search Tree
4Flatten a Multilevel Doubly Linked List

About the Construction & Serialization Pattern

Build a tree from its traversal orders, or convert a tree to/from a string representation. These test your understanding of how traversal orders uniquely define a tree's structure.

Key insight

Tree problems are almost always DFS (recursion) or BFS (level-order). The pattern: solve for children, combine results, return up. BST's sorted property lets you prune half the tree.

Common Trees Interview Problems

Maximum Depth of Binary Tree
Validate BST
Binary Tree Level Order Traversal
Lowest Common Ancestor
Serialize and Deserialize Binary Tree
Diameter of Binary Tree

Frequently Asked Questions

Why must the left subtree's rightmost node connect to the original right subtree?

In pre-order, the entire left subtree is visited before the right subtree begins, and the left subtree's last-visited node is its rightmost node. Splicing the old right subtree after that node preserves the exact pre-order sequence in the flattened list.

How does the O(1)-space approach compare with recursion here?

The pointer-rewiring loop uses constant extra space and O(n) amortized time, at the cost of trickier pointer surgery. The reverse pre-order recursion is shorter and less error-prone but consumes O(h) stack, which can matter on deeply skewed trees. Interviews often ask for both, so know the trade-off.