# 114. Flatten Binary Tree to Linked List (Medium)

Given a binary tree, flatten it to a linked list in-place.

For example, given the following tree:

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

The flattened tree should look like:

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

## Solutions

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

recurse(root);
}

private TreeNode recurse(TreeNode root) {
// return null if reach the end
if (root == null) {
return null;
}

// flatten left branch
TreeNode left = recurse(root.left);

// flatten right branch
TreeNode right = recurse(root.right);

// FIXME Do not forget to unlink to root.left
root.left = null;

if (left != null) {
// append right branch to the end of left branch if left exists
append(left, right);

// link root.right to the head of left branch if left exits.
// if left not exists, do not modify anything.
root.right = left;
}

return root;
}

private void append(TreeNode left, TreeNode right) {
while (left.right != null) {
left = left.right;
}

left.right = right;
}
}
``````