# [lintcode] Flatten Binary Tree to Linked List

#### Flatten Binary Tree to Linked List

Flatten a binary tree to a fake “linked list” in pre-order traversal.

Here we use the right pointer in TreeNode as the nextpointer in ListNode.

Have you met this question in a real interview?

Example

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

Note

Don’t forget to mark the left child of each node to null. Or you will get Time Limit Exceeded or Memory Limit Exceeded.

Challenge

Do it in-place without any extra memory.

```/**
* Definition of TreeNode:
* class TreeNode {
* public:
*     int val;
*     TreeNode *left, *right;
*     TreeNode(int val) {
*         this->val = val;
*         this->left = this->right = NULL;
*     }
* }
*/
class Solution {
public:
/**
* @param root: a TreeNode, the root of the binary tree
* @return: nothing
*/
void flatten(TreeNode *root) {
root = DFS(root, nullptr);
}
TreeNode* DFS(TreeNode *root, TreeNode * tail){
if(root == nullptr) return tail;
TreeNode * right = DFS(root->right, tail);
TreeNode * left = DFS(root->left, right);
root->right = left;
root->left = nullptr;
return root;
}
};```

Flatten binary tree, not a preorder approach. Functional correct but not an AC solution.

```/**
* Definition of TreeNode:
* class TreeNode {
* public:
*     int val;
*     TreeNode *left, *right;
*     TreeNode(int val) {
*         this->val = val;
*         this->left = this->right = NULL;
*     }
* }
*/
class Solution {
public:
/**
* @param root: a TreeNode, the root of the binary tree
* @return: nothing
*/
void flatten(TreeNode *root) {
if(root == nullptr) return ;
// move tail to right most node
while(tail->right){
tail = tail->right;
}