Flatten Binary Tree to Linked List

Medium#114pre-order

You get the root of a binary tree. Turn it, in place, into a list along the right links: every left link becomes none, and following right from the root gives the nodes in pre-order. Our tree: 4 with children 8 and 2; 8 has children 1 and 6; 2 has a left child, 5 — the answer is 4 → 8 → 1 → 6 → 2 → 5.

114 Flatten Binary Tree to Linked ListWalkthrough · 1×

Example: flatten a binary tree into a list along its right links, in pre-order and without extra memory.

482165via rightfrom the root42
not reached yetnode, and the link just changedlast: the last node of the left subtreealready in the list

node = root, 4

01/38
restart · back · play · step
Speed
1function flatten(root):
2 node = root
3 while node is not none:
4 if node.left is not none:
5 last = node.left
6 while last.right is not none:
7 last = last.right
8 last.right = node.right
9 node.right = node.left
10 node.left = none
11 node = node.right
12 return
state
node
–
last
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. In pre-order, a node's right subtree comes right after the last node of its left subtree. That node is found by going right from node.left until there is no right child.
  2. Hanging the right subtree there and moving the left subtree to the right keeps the pre-order and leaves node with no left link.
  3. node then steps right, so every node gets the same treatment, and the parts above node are already one list.

Complexity

Time O(n): node visits each node once, and last walks each right link at most once more. Memory O(1): two pointers, no stack, no recursion.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.