Pattern visualizer

Flatten Binary Tree to Linked List

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. 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]..

Morris-style pointer grafting

time O(n)space O(1)step 1 / 10

line 2

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

Where to practice Binary Trees

Practice Binary Trees problems All Binary Trees problems Back to roadmap