DSA Tracker

Visualize

Flatten Binary Tree to Linked List

Morris-style pointer grafting

time O(n)space O(1)

A preorder traversal visits a node, then its whole left subtree, then its whole right subtree. So in the final list, a node's original right subtree must come AFTER its entire left subtree. Grafting the old right subtree onto the rightmost node of the left subtree — then sliding the left subtree into the right pointer — builds that order using only the pointers already in the tree, no extra memory and no recursion stack.

Details

Animated on: Given the root of a binary tree, flatten the tree into a linked list in-place: the right pointer becomes 'next' and the left pointer is always null, in preorder order, for the tree [1, 2, 5, 3, 4, null, 6].

Problem:Flatten Binary Tree to Linked ListMedium

Morris-style pointer grafting

step 1 / 10

3
2
4
1
5
6

Flatten in place: every node's right pointer must end up pointing at the next node in preorder (1, 2, 3, 4, 5, 6), and every left pointer must become null. curr starts at the root, 1.

Pseudocode
1FUNCTION flatten(root):
2  curr <- root
3  WHILE curr != null:
4    IF curr.left != null:
5      pred <- curr.left
6      WHILE pred.right != null:
7        pred <- pred.right
8      pred.right <- curr.right
9      curr.right <- curr.left
10      curr.left <- null
11    curr <- curr.right
12  RETURN

← / → step · space play · Home restart

Every step in words

Show all 10 steps
  1. Flatten in place: every node's right pointer must end up pointing at the next node in preorder (1, 2, 3, 4, 5, 6), and every left pointer must become null. curr starts at the root, 1.
  2. curr = 1 has a left child. Walk right from 2 to find the rightmost node of that subtree — the predecessor is 4.
  3. Graft: 4.right <- 5 (curr's old right subtree moves behind the predecessor), then 1.right <- 2 and 1.left <- null. The left subtree is now spliced into the right chain.
  4. curr = 2 has a left child, 3. 3.right is already null, so 3 is its own rightmost node — the predecessor is 3.
  5. Graft: 3.right <- 4 (curr's old right subtree moves behind the predecessor), then 2.right <- 3 and 2.left <- null. The left subtree is now spliced into the right chain.
  6. curr = 3 has no left child, so there is nothing to graft. The right chain from here (3 -> 4 -> 5 -> 6) is already threaded correctly — curr just walks it to the end.
  7. curr = 4 has no left child, so there is nothing to graft. The right chain from here (4 -> 5 -> 6) is already threaded correctly — curr just walks it to the end.
  8. curr = 5 has no left child, so there is nothing to graft. The right chain from here (5 -> 6) is already threaded correctly — curr just walks it to the end.
  9. curr = 6 has no left child and no right child — the end of the list.
  10. Done. The tree is now a right-skewed list: 1 -> 2 -> 3 -> 4 -> 5 -> 6 — exactly the preorder of the original tree, rewired with no recursion stack and no extra storage (O(1) space).

Now solve it yourself

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

Solve Flatten Binary Tree to Linked List in the editorAll Binary Trees problemsBack to roadmap