> For the complete documentation index, see [llms.txt](https://chunhthanhde.gitbook.io/leetcode-top-interview/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://chunhthanhde.gitbook.io/leetcode-top-interview/topic-9-binary-tree-general/075-flatten-binary-tree-to-linked-list.md).

# 114. Flatten Binary Tree to Linked List 🔗

**Difficulty**: `Medium` - **Tags**: `Binary Tree`, `Depth-First Search (DFS)`, `Linked List`

[LeetCode Problem Link](https://leetcode.com/problems/flatten-binary-tree-to-linked-list/)

***

## Problem Statement 📜

Given the root of a binary tree, flatten the tree into a "linked list":

1. The "linked list" should use the same `TreeNode` class where:
   * The **right child pointer** points to the next node in the list.
   * The **left child pointer** is always `null`.
2. The "linked list" should follow the **pre-order traversal** of the binary tree.

***

## Examples 🌟

🔹 **Example 1**:

![](/files/NY9apGO3auoD8c7cuIq2)

**Input**:

```plaintext
root = [1,2,5,3,4,null,6]
```

**Output**:

```plaintext
[1,null,2,null,3,null,4,null,5,null,6]
```

**Explanation**:

The binary tree:

```plaintext
    1
   / \
  2   5
 / \    \
3   4    6
```

is flattened to:

```plaintext
1 -> 2 -> 3 -> 4 -> 5 -> 6
```

***

🔹 **Example 2**:

**Input**:

```plaintext
root = []
```

**Output**:

```plaintext
[]
```

***

🔹 **Example 3**:

**Input**:

```plaintext
root = [0]
```

**Output**:

```plaintext
[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** (using `O(1)` extra space)?

***

## Solution 💡

To solve this problem:

1. Use **pre-order traversal** to flatten the tree into a linked list.
2. Modify the `TreeNode` pointers **in-place** to achieve `O(1)` space complexity.

***

### Java Solution

```java
class Solution {
    public void flatten(TreeNode root) {
        if (root == null) return;

        TreeNode current = root;

        while (current != null) {
            // If the current node has a left child
            if (current.left != null) {
                // Find the rightmost node in the left subtree
                TreeNode rightmost = current.left;
                while (rightmost.right != null) {
                    rightmost = rightmost.right;
                }

                // Connect the rightmost node to the current's right subtree
                rightmost.right = current.right;

                // Move the left subtree to the right
                current.right = current.left;
                current.left = null;
            }

            // Move to the next node
            current = current.right;
        }
    }
}
```

***

## Explanation of the Solution

1. **Traversal**:
   * Start from the root and traverse down the tree using the right child.
2. **Rearranging Nodes**:
   * For each node:
     * If it has a left child, locate the **rightmost node** in the left subtree.
     * Attach the right subtree to the rightmost node.
     * Move the left subtree to the right and set the left child to `null`.
3. **In-place Modification**:
   * The tree is modified directly without using any extra space.

***

## Time Complexity ⏳

* **O(n)**: Each node is visited once.

## Space Complexity 💾

* **O(1)**: The tree is modified in-place without any extra data structures.

***

## Follow-up Challenges 🧐

* How would you approach the problem using recursion?
* Can you adapt this solution to work for a general graph structure?

You can find the full solution [here](https://github.com/ChunhThanhDe/Leetcode-Top-Interview/blob/main/Topic%209%20Binary%20Tree%20General/075%20Flatten%20Binary%20Tree%20to%20Linked%20List/Solution.java).


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://chunhthanhde.gitbook.io/leetcode-top-interview/topic-9-binary-tree-general/075-flatten-binary-tree-to-linked-list.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.