Flatten Binary Tree to Linked List
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 pre-order traversal of the binary tree.
Walk the tree in reverse-preorder: right, then left, then node. Maintain a single prev pointer; at each node set node.right = prev; node.left = null and update prev = node.
level-order: [1, 2, 5, 3, 4, _, 6]1 → 2 → 3 → 4 → 5 → 6def flatten(root):
prev = [None]
def visit(node):
if node is None: return
visit(node.right)
visit(node.left)
node.right = prev[0]
node.left = None
prev[0] = node
visit(root)function flatten(root) {
let prev = null;
function visit(node) {
if (!node) return;
visit(node.right);
visit(node.left);
node.right = prev;
node.left = null;
prev = node;
}
visit(root);
}class Solution {
TreeNode prev = null;
public void flatten(TreeNode root) {
if (root == null) return;
flatten(root.right);
flatten(root.left);
root.right = prev;
root.left = null;
prev = root;
}
}TreeNode* prev_ = nullptr;
void flatten(TreeNode* root) {
if (!root) return;
flatten(root->right);
flatten(root->left);
root->right = prev_;
root->left = nullptr;
prev_ = root;
}Explanation
We want the tree rewired into a right-leaning chain that follows pre-order (node, left, right). The neat trick is to build that chain backwards, from the last node to the first, using one moving prev pointer.
Pre-order is node, left, right. Reversed, that is right, left, node. So we recurse in exactly that order: visit(right), then visit(left), then handle the current node. By the time we touch a node, prev already points at whatever should come after it in the final list.
At each node we set node.right = prev, clear node.left = null, and then update prev = node. Each node simply hooks itself onto the front of the growing chain.
Example: tree [1, 2, 5, 3, 4, _, 6]. We visit 6 first (prev was null), then 5 points to 6, then the left side 4, 3, 2, and finally the root 1. Reading right pointers from the root gives 1 → 2 → 3 → 4 → 5 → 6.
Each node is visited once and rewired in constant work, so this is O(n) time using only the recursion stack.