Skip to main content

114. Flatten Binary Tree to Linked List

medium

Rewire a binary tree in place so every node's left is null and right follows a preorder traversal. The reverse-postorder twist solves it without extra storage — a classic in-place tree transform.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Given the root of a binary tree, flatten the tree into a 'linked list': the linked list should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null. The linked list should be in the same order as a preorder traversal of the binary tree.

Constraints

  • The number of nodes in the tree is in the range [0, 2000].
  • -100 <= Node.val <= 100

Examples

Example 1

Input
root = [1,2,5,3,4,null,6]
Output
[1,null,2,null,3,null,4,null,5,null,6]

Example 2

Input
root = []
Output
[]

Example 3

Input
root = [0]
Output
[0]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Preorder is root, left subtree, right subtree — so the flattened list goes node, then the flattened left, then the flattened right.

Hint 2

If you flatten in reverse-postorder (right, left, root) and keep a running 'prev' pointer, you can splice as you go.

Hint 3

Iterative without recursion: at each node, find the rightmost node of its left subtree and graft the current right onto it. Then move left to right and null out left. Repeat.

Solution approach

Reveal approach

Two clean options. (1) Reverse-postorder recursion: walk right, then left, then root, tracking prev (initially null). At each node: node.right = prev; node.left = null; prev = node. This rewrites pointers safely because each subtree is processed before its parent. (2) Iterative O(1) extra space: while curr is not null, if curr.left is not null, find rightmost = curr.left while walking right pointers; set rightmost.right = curr.right; set curr.right = curr.left; set curr.left = null. Move curr = curr.right. This grafts the left subtree into the right chain and nulls the left at each step. O(n) time. Recursive uses O(h) stack; iterative is O(1) extra space.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • tree-dfs
  • recursion
  • linked-list

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Meta
  • Microsoft
  • Bloomberg

More Trees practice problems

See all Trees problems →