# LeetCode 114. Flatten Binary Tree to Linked List

## Description

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.

Example 1:

```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 = 
Output: 
```

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

## Explanation

Recursively find the leftmost leaf node and start from there to add the root.right and replace root.right with root.left.

## Python Solution

``````# 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:
def flatten(self, root: TreeNode) -> None:
"""
Do not return anything, modify root in-place instead.
"""

self.helper(root)

def helper(self, root):
if not root:
return None

if not root.left and not root.right:
return root

left_tail = self.helper(root.left)
right_tail = self.helper(root.right)

if left_tail:
left_tail.right = root.right
root.right = root.left
root.left = None

if right_tail:
return right_tail

return left_tail``````
• Time Complexity: O(N).
• Space Complexity: O(N).