# Flatten Binary Tree to Linked List
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/flatten-binary-tree-to-linked-list)
Canonical: https://scaleengineer.com/dsa/problems/flatten-binary-tree-to-linked-list
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Linked List, Stack, Tree, Binary Tree
**Companies:** [Apple](https://scaleengineer.com/companies/apple), [Google](https://scaleengineer.com/companies/google), [Myntra](https://scaleengineer.com/companies/myntra), [PayPal](https://scaleengineer.com/companies/paypal), [Uber](https://scaleengineer.com/companies/uber), [Yahoo](https://scaleengineer.com/companies/yahoo), [Salesforce](https://scaleengineer.com/companies/salesforce), [Media.net](https://scaleengineer.com/companies/media.net), [Anduril](https://scaleengineer.com/companies/anduril)
---
## 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**](https://en.wikipedia.org/wiki/Tree%5Ftraversal#Pre-order,%5FNLR) of the binary tree.

**Example 1:**

![](https://assets.glich.co/dsa/flatten-binary-tree-to-linked-list/image0.jpg) 

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

# Approaches
## Brute Force using Extra Space
This approach involves performing a pre-order traversal of the binary tree and storing each visited node in an auxiliary list. After the traversal is complete, the list contains all nodes in the desired flattened order. We then iterate through this list, rearranging the `left` and `right` pointers of each node to form the linked list structure.
**Time:** O(N) · **Space:** O(N)
**Pros:** Very straightforward and easy to understand.; The logic directly follows the definition of the problem (get pre-order sequence, then link them).
**Cons:** Requires O(N) extra space for the list, which is inefficient and does not satisfy the follow-up constraint of O(1) space.
### Explanation
The core idea is to separate the traversal from the restructuring. First, we perform a standard pre-order traversal (Root, Left, Right) on the tree. We can use a recursive helper function for this. During the traversal, every node we encounter is added to a dynamic array or list. Once the traversal is complete, this list holds all the tree nodes in the exact sequence required for the flattened list.
The second step is to iterate through this list of nodes from the beginning. For each node at index `i`, we set its `left` child to `null` and its `right` child to the node at index `i+1`. This process effectively links all the nodes together. The last node in the list will have its `right` child set to `null`, terminating the flattened list.
```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        List<TreeNode> nodes = new ArrayList<>();
        preorderTraversal(root, nodes);
        
        for (int i = 0; i < nodes.size() - 1; i++) {
            TreeNode curr = nodes.get(i);
            TreeNode next = nodes.get(i + 1);
            curr.left = null;
            curr.right = next;
        }
        
        // Set the last node's children to null
        TreeNode lastNode = nodes.get(nodes.size() - 1);
        lastNode.left = null;
        lastNode.right = null;
    }
    
    private void preorderTraversal(TreeNode node, List<TreeNode> nodes) {
        if (node == null) {
            return;
        }
        nodes.add(node);
        preorderTraversal(node.left, nodes);
        preorderTraversal(node.right, nodes);
    }
}
```
### Algorithm
- If the `root` is `null`, return immediately.
- Create an empty `List<TreeNode>` to store the nodes.
- Perform a pre-order traversal on the tree. In the traversal, add each visited node to the list.
- Iterate through the list from the first element up to the second-to-last element.
- For each node at index `i`, set its `left` pointer to `null` and its `right` pointer to the node at index `i+1`.
- Set the `left` and `right` pointers of the last node in the list to `null`.

## Recursive In-place Solution (Right, Left, Root Traversal)
A more space-efficient approach is to use recursion in-place. By traversing the tree in a modified post-order fashion (Right -> Left -> Root), we can flatten the tree. We maintain a pointer to the previously processed node (`prev`). For each node, we first recursively flatten its right subtree, then its left subtree. Finally, we wire the current node to point to the head of the previously flattened part (`prev`) and update `prev` to be the current node.
**Time:** O(N) · **Space:** O(H)
**Pros:** Solves the problem in-place without requiring an auxiliary list.; It's a clever recursive solution that is more space-efficient than the brute-force approach on average.
**Cons:** Uses the recursion call stack for space, which can be O(H) where H is the height of the tree. In the worst case of a skewed tree, this becomes O(N), failing the strict O(1) space constraint.
### Explanation
This approach avoids using an explicit list by performing the rewiring during the recursion itself. The key insight is to process the subtrees in a specific order: Right, Left, Root. This is a variation of a post-order traversal. We use a helper variable, `prev`, which keeps track of the node that was processed last (which will be the head of the already-flattened part of the tree).
The recursive function works as follows:
1. It first calls itself on the right child. This flattens the entire right subtree. After this call returns, `prev` will point to the head of the flattened right subtree.
2. Then, it calls itself on the left child. This flattens the left subtree. The tail of this flattened left subtree will be internally linked to the `prev` from the previous step. After this call returns, `prev` will point to the head of the flattened left subtree.
3. Finally, it processes the current node. It sets the current node's `right` pointer to `prev` (linking it to the rest of the flattened list) and its `left` pointer to `null`. It then updates `prev` to be the current node, making it the new head of the flattened list seen so far.
By starting the process from the root, the entire tree is flattened in-place.
```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private TreeNode prev = null;

    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        // Traverse right subtree first, then left, then process the root
        flatten(root.right);
        flatten(root.left);
        
        // Rewire the current node
        root.right = prev;
        root.left = null;
        
        // Update prev to the current node for the next step up in recursion
        prev = root;
    }
}
```
### Algorithm
- Initialize a global or class-level `TreeNode` variable `prev` to `null`. This will track the previously visited node.
- Define a recursive function `flatten(node)`.
- Base Case: If `node` is `null`, return.
- Recursively call `flatten(node.right)`.
- Recursively call `flatten(node.left)`.
- After the recursive calls, set `node.right` to `prev`.
- Set `node.left` to `null`.
- Update `prev` to be the current `node`.
- Call the initial `flatten(root)`.

## Optimal Iterative In-place Solution (Morris Traversal)
The most optimal solution achieves O(1) space complexity by modifying the tree in-place using an iterative approach inspired by Morris Traversal. We traverse the tree with a `current` pointer. If the `current` node has a left child, we find the rightmost node of its left subtree (the pre-order predecessor). We then link this predecessor's `right` pointer to the `current` node's `right` child and move the entire left subtree to become the `current` node's new `right` child. This process effectively flattens the tree without using extra space for a stack or list.
**Time:** O(N) · **Space:** O(1)
**Pros:** Achieves optimal O(1) space complexity, satisfying the follow-up.; It's an in-place, iterative solution that avoids recursion overhead.
**Cons:** The logic can be less intuitive to grasp compared to the recursive or list-based approaches.; The pointer manipulation is more complex.
### Explanation
This iterative solution is the most space-efficient, achieving true O(1) extra space. It's based on the principles of Morris Traversal. The algorithm iterates through the tree, modifying pointers as it goes to create the flattened structure without a stack or recursion.
We use a `curr` pointer, starting at the root. In each step of the main loop:
- If `curr` has no left child, it means we are already in the correct pre-order position relative to its children. We simply move to the right child (`curr = curr.right`) to continue.
- If `curr` has a left child, we need to insert the left subtree between `curr` and `curr.right`. To do this, we first find the rightmost node of the left subtree. This node is the pre-order predecessor of `curr`'s original right child. We then perform the rewiring:
    1. Set the predecessor's `right` pointer to `curr.right`.
    2. Move the entire left subtree to `curr.right`.
    3. Set `curr.left` to `null`.
After this rewiring, we move `curr` to its new right child (the former left child) and continue the process. The loop terminates when `curr` becomes `null`.
```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public void flatten(TreeNode root) {
        TreeNode curr = root;
        while (curr != null) {
            if (curr.left != null) {
                // Find the rightmost node in the left subtree
                TreeNode predecessor = curr.left;
                while (predecessor.right != null) {
                    predecessor = predecessor.right;
                }
                
                // Rewire the pointers
                predecessor.right = curr.right; // Connect predecessor to curr's right child
                curr.right = curr.left;         // Move left subtree to the right
                curr.left = null;               // Set left child to null
            }
            // Move to the next node in the pre-order sequence
            curr = curr.right;
        }
    }
}
```
### Algorithm
- Initialize a pointer `curr` to `root`.
- Start a `while` loop that continues as long as `curr` is not `null`.
- Inside the loop, check if `curr.left` is not `null`.
- If it is, find the rightmost node of the left subtree. Let's call it `predecessor`.
  - Start with `predecessor = curr.left`.
  - While `predecessor.right` is not `null`, update `predecessor = predecessor.right`.
- Perform the rewiring:
  - `predecessor.right = curr.right`
  - `curr.right = curr.left`
  - `curr.left = null`
- Whether `curr.left` was null or not, move to the next node by updating `curr = curr.right`.
- The loop continues until the entire tree is processed.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public void flatten ( TreeNode root ) { while ( root != null ) { if ( root . left != null ) { TreeNode pre = root . left ; while ( pre . right != null ) { pre = pre . right ; } pre . right = root . right ; root . right = root . left ; root . left = null ; } root = root . right ; } } }
```

### JavaScript

```javascript
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @return {void} Do not return anything, modify root in-place instead. */ var flatten =
  function (root) {
    while (root) {
      if (root.left) {
        let pre = root.left;
        while (pre.right) {
          pre = pre.right;
        }
        pre.right = root.right;
        root.right = root.left;
        root.left = null;
      }
      root = root.right;
    }
  };

```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: void flatten ( TreeNode * root ) { while ( root ) { if ( root -> left ) { TreeNode * pre = root -> left ; while ( pre -> right ) { pre = pre -> right ; } pre -> right = root -> right ; root -> right = root -> left ; root -> left = nullptr ; } root = root -> right ; } } };
```

### Python

```python
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : # stack, pre-order interation def flatten ( self , root : TreeNode ) -> None : """ Do not return anything, modify root in-place instead. """ if not root : return stack = [ root ] prev = TreeNode ( 0 ) # dummy node while stack : current = stack . pop () if current . right : stack . append ( current . right ) if current . left : stack . append ( current . left ) prev . left = None prev . right = current prev = current ########### class Solution : # no stack def flatten ( self , root : Optional [ TreeNode ]) -> None : """ Do not return anything, modify root in-place instead. """ while root : if root . left : pre = root . left while pre . right : # start feom right pre = pre . right pre . right = root . right root . right = root . left root . left = None root = root . right
```