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.

Description Hints 1 Solution Video 14:27

114. Flatten Binary Tree to Linked List

Medium71.6% acceptance8 companies

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)?

Asked at 8 companies

Josh Technology Microsoft Anduril

Google Amazon Meta Bloomberg Oracle

Topics

Hints open one at a time

Hint 1

If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.

14:27

Still stuck?Read 4 approaches, or watch a walkthrough.

Open solution