# LeetCode: 114. Flatten Binary Tree to Linked List

**The 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
of the binary tree.**pre-order traversal**

**Example**

```
Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]
```

**Constraints:**

- The number of nodes in the tree is in the range
`[0, 2000]`

. `-100 <= Node.val <= 100`

**Solution**

We opted for a recursive approach to tackle this problem, and upon evaluating our solution on the LeetCode platform, we achieved the following outcome:

Here's the code that led us to this result.

```
void flatten(TreeNode* root) {
vector<short> preorder;
flattenHelper(root, preorder);
TreeNode *&head = root;
for(int i = 1; i < preorder.size(); ++i){
if(head->right == NULL) {
head->right = new TreeNode(preorder[i]);
}else {
head->right->val = preorder[i];
}
head->left = NULL;
head = head->right;
}
}
void flattenHelper(TreeNode* root, vector<short> &preorder) {
if (root == NULL) return;
preorder.push_back((short)root->val);
flattenHelper(root->left, preorder);
flattenHelper(root->right, preorder);
}
```

Here's an explanation of the code:

1. `void flatten(TreeNode* &root)`

: This is the main function for flattening the binary tree. It takes a reference to a pointer to a `TreeNode`

as an argument, which allows the function to modify the root of the tree if necessary.

2. `vector<short> preorder;`

: This vector will be used to store the values of the tree nodes in pre-order traversal order.

3. `flattenHelper(root, preorder);`

: This line calls the `flattenHelper`

function to perform a pre-order traversal of the binary tree and populate the `preorder`

vector with the values of the nodes.

4. `TreeNode *&head = root;`

: This line declares a reference to a pointer to a `TreeNode`

named `head`

and initializes it with the same value as the `root`

pointer. The reference allows us to update the `root`

pointer as we build the flattened linked list.

5. The `for`

loop iterates through the `preorder`

vector starting from index 1 (skipping the root node, as it's already the head of the flattened list).

6. Inside the loop:

- If
`head->right`

is`NULL`

, it means that there's no right child node in the flattened list yet. In this case, a new`TreeNode`

is created with the value from the`preorder`

vector, and it's assigned as the right child of the current`head`

. - If
`head->right`

is not`NULL`

, it means that the right child node already exists, so its value is updated with the value from the`preorder`

vector. `head->left`

is set to`NULL`

because we are building a singly linked list.`head`

is updated to`head->right`

, moving to the next node in the flattened list.

7. `void flattenHelper(TreeNode* root, vector<short> &preorder)`

: This is a recursive helper function that performs a pre-order traversal of the binary tree.

- If
`root`

is`NULL`

, the function returns early. - Otherwise, the value of the current node (
`root->val`

) is added to the`preorder`

vector. - The function then recursively calls itself on the left and right subtrees of the current node.