Flatten Binary Tree to Linked List

LeetCode 114 • Medium • Trees • Anduril

Flatten a binary tree to a right-linked list in preorder, in-place. Demo: 1→2→3→4→5.

TimeO(n)visit each node once

SpaceO(h)explicit stack

Current

Tree

Flat spine

stack—

prev—

node—

spine—

Speed:

Ready

Press Play to walk the algorithm.

Whiteboard

Size:3

Type It — Iterative

flatten(root) — mutate tree so it becomes a right-only linked list (preorder). Iterative stack: push right then left, rewire prev.

═══ FLATTEN BT — ITERATIVE PREORDER ═══

PATTERN ▸ stack preorder + prev rewire O(n) · O(h)

① EDGE

if not root: return

② INIT

stack = [root]

prev = None

③ LOOP (preorder)

node = stack.pop()

push right first, then left (so left is next)

④ REWIRE

if prev: prev.right = node; prev.left = None

prev = node

your implementation

Verify:

Type It — Recursive

flatten(root) — mutate tree so it becomes a right-only linked list (preorder). Recurse children, then splice left onto right.

═══ FLATTEN BT (LC 114) ═══

PATTERN ▸ postorder splice

① flatten(right); flatten(left)

② if left: rightmost(left).right = root.right

root.right = root.left; root.left = None

your implementation

Verify: