Skip to main content
Talentd

Flatten Binary Tree to Linked List - Solution & Explanation

MediumLinked ListStackTreeDepth-First Search23 min readAsked at: Amazon, Microsoft, Meta +5
Practice this problem

Problem Statement

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 pre-order traversal of the binary tree.

 

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]

 

Constraints:

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

 

Follow up: Can you flatten the tree in-place (with O(1) extra space)?

Approach Overview

Problem Overview: You receive the root of a binary tree and must transform it into a linked list in-place. The linked list should follow the same order as a preorder traversal (root β†’ left β†’ right). Every node’s left pointer becomes null, and the right pointer acts as the next pointer in the list.

Approach 1: Recursive Pre-order Traversal (O(n) time, O(h) space)

This approach uses a classic Depth-First Search recursion that processes nodes in preorder. Maintain a reference to the previously visited node. During traversal, set prev.right = current and prev.left = null to build the linked structure incrementally. The key insight is to traverse the right subtree after the left while rewiring pointers as you go. Time complexity is O(n) because each node is visited once. Space complexity is O(h), where h is the tree height due to the recursion stack.

Approach 2: Iterative Pre-order Traversal with Stack (O(n) time, O(n) space)

This method simulates preorder traversal using an explicit stack. Push the root node first. For each popped node, push its right child and then its left child so the left subtree is processed next. Rewire pointers by setting the current node’s right pointer to the next node on the stack and clearing left. The stack preserves preorder ordering without recursion. Time complexity remains O(n) since each node is pushed and popped once. Space complexity becomes O(n) in the worst case for skewed trees.

Both methods restructure the Binary Tree in-place without creating new nodes. The recursive approach is compact and mirrors the definition of preorder traversal. The iterative stack approach avoids recursion depth limits and provides more explicit control over traversal order.

Recommended for interviews: The recursive preorder DFS is usually the expected explanation because it clearly demonstrates pointer manipulation during traversal. Interviewers want to see that you understand preorder processing and in-place tree modification. The iterative stack version is a strong alternative when discussing recursion limits or implementing traversal without the call stack.

Approach 1: Recursive Pre-order Traversal

This approach involves a recursive pre-order traversal of the tree. The idea is to recursively flatten the left and right subtrees, then append the flattened left subtree between the root and the flattened right subtree.

The steps are as follows:

  1. Recursively flatten the left and right subtrees.
  2. Save the right subtree, then set the root's right to the left subtree and left to null.
  3. Traverse to the end of the new right subtree (originally left subtree) and append the saved right subtree.

This leverage the pre-order traversal principle: Root → Left → Right.

This code defines a flatten function for recursively transforming a binary tree into a linked list in pre-order format. It first flattens the left and right subtrees, then rearranges the pointers of the root node.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) where n is the number of nodes in the tree since each node is visited once.
Space Complexity: O(n) due to the recursive call stack on an unbalanced tree.

Try this approach in the editor β†’

Approach 2: Iterative Pre-order Traversal

This approach simplifies the recursive method by using a stack to maintain state information. By using controlled use of stack structures, we can modify the tree iteratively.

The algorithm progresses with these steps:

  1. Construct a stack and push the root.
  2. Process nodes using a stack to handle traversal iteratively, similar to pre-order.
  3. While processing each node, capture its left and right children, alter pointers, and advance the iteration.

This achieves similar logic as recursion but without directly using the call stack by using our custom stack for maintaining traversal state.

This C code leverages a custom stack to iteratively implement pre-order traversal. Nodes are processed such that when a node is visited, it pushes its right and left children onto the stack. The list is reordered inline using right field connections.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) because every node is processed once.
Space Complexity: O(n), matching the worst-case stack usage when all nodes are in a single path.

Try this approach in the editor β†’

Approach 3: Find Predecessor Node

The visit order of preorder traversal is "root, left subtree, right subtree". After the last node of the left subtree is visited, the right subtree node of the root node will be visited next.

Therefore, for the current node, if its left child node is not null, we find the rightmost node of the left subtree as the predecessor node, and then assign the right child node of the current node to the right child node of the predecessor node. Then assign the left child node of the current node to the right child node of the current node, and set the left child node of the current node to null. Then take the right child node of the current node as the next node and continue processing until all nodes are processed.

The time complexity is O(n), where n is the number of nodes in the tree. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor β†’

Approach 4: Default Approach

Code

Go

Go

Try this approach in the editor β†’

Complexity Comparison

ApproachComplexity
Recursive Pre-order Traversal

Time Complexity: O(n) where n is the number of nodes in the tree since each node is visited once.
Space Complexity: O(n) due to the recursive call stack on an unbalanced tree.

Iterative Pre-order Traversal

Time Complexity: O(n) because every node is processed once.
Space Complexity: O(n), matching the worst-case stack usage when all nodes are in a single path.

Find Predecessor Nodeβ€”
Default Approachβ€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive Pre-order TraversalO(n)O(h)Preferred in interviews; concise DFS logic and natural preorder traversal
Iterative Pre-order Traversal (Stack)O(n)O(n)When avoiding recursion or handling deep trees where recursion depth could overflow

Video Solution

L38. Flatten a Binary Tree to Linked List | 3 Approaches | C++ | Java β€’ take U forward β€’ 328,381 views views

Watch 9 more video solutions β†’

Frequently Asked Questions

Is Flatten Binary Tree to Linked List easy or hard?
Flatten Binary Tree to Linked List is generally classified as a medium difficulty problem. The traversal itself is straightforward, but correctly modifying pointers in-place while preserving preorder order requires careful reasoning about tree structure.
Flatten Binary Tree to Linked List Python/Java solution
Python and Java solutions typically implement preorder DFS. The recursive version keeps a global or class-level previous node reference and updates pointers while traversing. An alternative iterative solution uses a stack to simulate preorder traversal while rewiring nodes in-place.
How to solve Flatten Binary Tree to Linked List in O(n)?
Perform a preorder traversal of the tree and rewire pointers during the visit. For each node, set the previous node’s right pointer to the current node and clear the left pointer. Continue processing left then right children. This ensures each node is processed once, giving O(n) time complexity.
What is the best approach for Flatten Binary Tree to Linked List?
The most common approach uses preorder depth-first traversal and rewires pointers while visiting nodes. A recursive DFS keeps track of the previously visited node and connects it to the current node using the right pointer. This runs in O(n) time and O(h) space where h is the tree height. Many interviewers expect this preorder-based solution.
Is Flatten Binary Tree to Linked List asked at Google/Amazon/Meta?
Flatten Binary Tree to Linked List is a common medium-level binary tree problem frequently reported in interviews at companies like Amazon, Google, Meta, and Microsoft. It tests depth-first traversal, pointer manipulation, and understanding of tree structure transformations.
What data structure is used in Flatten Binary Tree to Linked List?
The problem primarily uses binary trees combined with depth-first search traversal. Implementations often rely on recursion or an explicit stack to maintain preorder traversal order. The final structure behaves like a singly linked list using the right pointer.
What is the time complexity of Flatten Binary Tree to Linked List?
The time complexity is O(n) because every node in the binary tree is visited exactly once during traversal. Pointer updates are constant-time operations for each node. Space complexity is O(h) with recursion or O(n) when using an explicit stack in the iterative approach.

Ready to solve this problem?

Practice Flatten Binary Tree to Linked List with our built-in code editor and test cases.

Practice on FleetCode
Previous

Correct a Binary Tree

Next

Flatten a Multilevel Doubly Linked List