Skip to content

Flatten to Linked List

Rearranging Pointers In-Place

Problem (LC 114): Flatten a binary tree into a "linked list" in-place. The linked list should use the right pointer as next, the left pointer should always be nullptr, and the order should match preorder traversal.

      1                1
     / \                \
    2   5      →         2
   / \   \                \
  3   4   6                3
                            \
                             4
                              \
                               5
                                \
                                 6

Preorder: [1, 2, 3, 4, 5, 6]. The flattened list follows this order, using only right pointers.

The constraint "in-place" means: don't create new nodes. Rewire the existing pointers.

The Naive Approach: Collect and Rewire

You could do a preorder traversal, collect all nodes in a vector, then link them:

nodes[0]->right = nodes[1];  nodes[0]->left = nullptr;
nodes[1]->right = nodes[2];  nodes[1]->left = nullptr;
...

This works but uses \(O(n)\) extra space. Can you do it in \(O(1)\) space?

The Reverse Postorder Trick

Here's the idea that makes this problem elegant. Think about what happens if you process nodes in reverse preorder — that's right, left, root (the opposite of preorder's root, left, right).

For our tree, reverse preorder visits: 6, 5, 4, 3, 2, 1.

Now imagine you keep a pointer called previousNode, starting at nullptr. Each time you visit a node:

  1. Set node->right = previousNode (link to the previously processed node)
  2. Set node->left = nullptr (clear the left pointer)
  3. Update previousNode = node

You're building the linked list from the tail backward.

Reverse postorder builds the flattened list from tail to head

Full Trace

Step Visit Node previousNode Before Set right → Set left → previousNode After
1 6 nullptr 6->right = nullptr 6->left = nullptr 6
2 5 6 5->right = 6 5->left = nullptr 5
3 4 5 4->right = 5 4->left = nullptr 4
4 3 4 3->right = 4 3->left = nullptr 3
5 2 3 2->right = 3 2->left = nullptr 2
6 1 2 1->right = 2 1->left = nullptr 1

After step 6, the tree is flattened: 1 → 2 → 3 → 4 → 5 → 6 → nullptr.

Why reverse postorder? If you processed in preorder (1, 2, 3, ...), modifying node 1's right pointer would destroy the link to node 5 before you could visit it. By going in reverse, you only modify nodes you've already finished with.

The Code

TreeNode* previousNode = nullptr;

void flatten(TreeNode* root) {
    if (!root) return;
    flatten(root->right);
    flatten(root->left);
    root->right = previousNode;
    root->left = nullptr;
    previousNode = root;
}

Complexity: \(O(n)\) time, \(O(h)\) space (recursion stack).

The global variable previousNode is fine for a standalone solution. In an interview, you'd wrap it in a class or pass it by reference to avoid globals.

The Morris-Style Approach: True O(1) Space

There's a way to flatten without recursion and without a stack — \(O(1)\) extra space.

The idea: for each node that has a left child, find the rightmost node in the left subtree. That rightmost node should point to the current node's right child. Then move the left subtree to the right and clear the left pointer.

This is the same pointer-threading idea behind Morris traversal. You're temporarily rewiring the tree to encode the traversal order in the pointers themselves.

Full Trace

Starting tree:

      1
     / \
    2   5
   / \   \
  3   4   6

Morris-style flatten rewires the rightmost node of the left subtree

Step Current Has Left? Rightmost of Left Subtree Action
1 1 Yes (→2) 4 (rightmost in subtree rooted at 2) 4->right = 5, 1->right = 2, 1->left = null
2 2 Yes (→3) 3 (rightmost in subtree rooted at 3) 3->right = 4, 2->right = 3, 2->left = null
3 3 No — move to 3->right = 4
4 4 No — move to 4->right = 5
5 5 No — move to 5->right = 6
6 6 No — move to 6->right = nullptr, done

After step 1, the tree looks like:

  1
   \
    2
   / \
  3   4
       \
        5
         \
          6

After step 2:

  1
   \
    2
     \
      3
       \
        4
         \
          5
           \
            6

Steps 3-6 just walk the chain — no modifications needed.

The Code

void flattenIterative(TreeNode* root) {
    TreeNode* current = root;
    while (current) {
        if (current->left) {
            TreeNode* rightmost = current->left;
            while (rightmost->right) {
                rightmost = rightmost->right;
            }
            rightmost->right = current->right;
            current->right = current->left;
            current->left = nullptr;
        }
        current = current->right;
    }
}

Complexity: \(O(n)\) time, \(O(1)\) space.

The time is still \(O(n)\) despite the inner while loop. Each edge is traversed at most twice (once during the rightmost search, once during the main traversal), so the total work is \(O(n)\).

Connection to Morris Traversal

Morris traversal uses the same trick: find the inorder predecessor, create a temporary thread, use it to return to the parent without a stack. Here, we're creating permanent links (the flattened list IS the final structure), but the pointer-manipulation technique is identical.

If you understand flatten-to-linked-list, you understand the core of Morris traversal. The difference is that Morris creates temporary links and removes them afterward, while flatten creates permanent links.

Try It

The starter code has a flatten function with a TODO. Implement the reverse postorder approach.

Input: [1, 2, 5, 3, 4, null, 6]
Output: 1 2 3 4 5 6 (following right pointers)

Predict before running: What happens with a single-node tree? flatten(root) calls flatten(nullptr) twice (left and right), both return immediately. Then root->right = nullptr (previousNode is null), root->left = nullptr. The single node is already a valid "linked list." Correct.

Challenge: Can you flatten in postorder instead of preorder? What changes in the approach? (Hint: reverse postorder of a postorder sequence is... preorder. So you'd process in preorder and link backward.)

Edge Cases to Watch For

  • Global variable reset: The reverse postorder approach uses a global previousNode. If you call flatten on multiple trees without resetting previousNode = nullptr, the second tree's tail links to the first tree. In an interview, wrap it in a class or pass by reference to avoid this cross-contamination.

Problems

Problem Link Difficulty
LC 114 — Flatten Binary Tree to Linked List leetcode.com/problems/flatten-binary-tree-to-linked-list Medium
LC 430 — Flatten a Multilevel Doubly Linked List leetcode.com/problems/flatten-a-multilevel-doubly-linked-list Medium
LC 897 — Increasing Order Search Tree leetcode.com/problems/increasing-order-search-tree Easy