Flatten Binary Tree to Linked List — Problem & Solution
Flatten Binary Tree to Linked List solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Flatten Binary Tree to Linked List is a medium coding problem on depth-first search, trees and stack, asked in Amazon, Microsoft and Meta interviews.
- Difficulty: Medium
- Topics: Depth-First Search, Trees, Stack
- Asked at: Amazon, Microsoft, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given the root of a binary tree, flatten it in place into a "linked list" made of the same nodes:
- the list follows the tree's preorder (node, left subtree, right subtree);
- each node's
rightpointer points to the next node of the list, and itsleftpointer is null.
Return the root once the tree is flattened.
Example 1
Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]
Explanation: The preorder is 1, 2, 3, 4, 5, 6; each node becomes the right child of the one before it.
Example 2
Input: root = []
Output: []
Explanation: An empty tree stays empty.
Example 3
Input: root = [0]
Output: [0]
Explanation: A single node is already a list.
Constraints
0 <= number of nodes <= 2000-100 <= Node.val <= 100
Follow-up: Can you flatten the tree with O(1) extra space?
Hints for Flatten Binary Tree to Linked List
Hint 1
In preorder, a node's whole left subtree comes right after it, and its right subtree comes after the last node of the left subtree.
Hint 2
The last node of a left subtree in preorder is its rightmost node — follow
rightpointers from the left child until there are none.Hint 3
At each node with a left child: hang the node's right subtree off that rightmost node, move the left subtree to the right, clear the left pointer, then continue to the right.
How to solve Flatten Binary Tree to Linked List
Splice each left subtree in between a node and its right subtree. The left subtree's last preorder node — its rightmost node — is where the old right subtree reattaches. Doing this top-down along the right spine flattens the tree with no stack.
Approach
- Let
curbe the root. - While
curis not null: if it has a left child, findpre, the rightmost node of the left subtree. - Set
pre.right = cur.right, thencur.right = cur.leftandcur.left = null. - Move
curtocur.rightand repeat. - Return the root.
Why it works
After the splice, the order that follows cur is: its old left subtree (in which pre is the last node in preorder) and then its old right subtree — exactly the preorder of cur's subtree. The splice keeps every subtree's internal preorder, and the walk then repeats the step on every node of the new right chain, so when it ends no left pointer remains and the chain is the full preorder.
Complexity
- Time —
O(n): each node is passed over a constant number of times ascurand as part of a rightmost search - Space —
O(1)
Pitfalls
- Save the right subtree before overwriting
cur.right, or it is lost. - Clear
lefton every node — a list node with a leftover left child is not flattened.
Reference solution
Python
from typing import Optional
def flatten(root: Optional[TreeNode]) -> Optional[TreeNode]:
cur = root
while cur:
if cur.left:
pre = cur.left
while pre.right:
pre = pre.right
pre.right = cur.right
cur.right = cur.left
cur.left = None
cur = cur.right
return rootJava
public static TreeNode flatten(TreeNode root) {
TreeNode cur = root;
while (cur != null) {
if (cur.left != null) {
TreeNode pre = cur.left;
while (pre.right != null) pre = pre.right;
pre.right = cur.right;
cur.right = cur.left;
cur.left = null;
}
cur = cur.right;
}
return root;
}C++
TreeNode* flatten(TreeNode* root) {
TreeNode* cur = root;
while (cur) {
if (cur->left) {
TreeNode* pre = cur->left;
while (pre->right) pre = pre->right;
pre->right = cur->right;
cur->right = cur->left;
cur->left = nullptr;
}
cur = cur->right;
}
return root;
}JavaScript
var flatten = function(root) {
var cur = root;
while (cur !== null) {
if (cur.left !== null) {
var pre = cur.left;
while (pre.right !== null) pre = pre.right;
pre.right = cur.right;
cur.right = cur.left;
cur.left = null;
}
cur = cur.right;
}
return root;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals