## # 114. Flatten Binary Tree to Linked List

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
``````

### # Solution

Approach 1: recursive solution. Assume that root's left and right subtree are already flattened, we need to hook up the right subtree to left's last node. Therefore we need a helper that returns the last node after flattening.

Approach 2: iterative solution. Keep putting the right subtree under the rightmost leaf in left subtree, then set the left subtree to be the right subtree.

Approach 3: Preorder simulation. For example, iterative solution using stack -- similar to stack based solution for Binary Tree Preorder Traversal, we push right subtree then left subtree onto the stack.

Approach 4: Reverse-postorder simulation.

Approach 5: Inorder simulation.

### # Code (Python)

Approach 1:

``````    def flatten(self, root):
# recursive solution
if not root:
return
self._helper(root)

def _helper(self, node):
# this helper assumes node is not None, and it flattens and returns the last non-None node
if not node.left and not node.right:
return node
elif not node.left:
return self._helper(node.right)
elif not node.right:
returned_node = self._helper(node.left)
node.right = node.left
node.left = None
return returned_node
else:
left_last = self._helper(node.left)
right_last = self._helper(node.right)
left_last.right = node.right
node.right = node.left
node.left = None
return right_last
``````

Approach 2:

``````    def flatten(self, root):
if not root:
return
node = root
while node:
if node.left:
current = node.left
while current.right:
current = current.right
current.right = node.right
node.right = node.left
node.left = None
node = node.right
``````

Approach 3:

``````    def flatten(self, root):
# iterative -- stack based preorder traversal
if not root:
return
prev_node = None
stack = [root]
while stack:
node = stack.pop()
if prev_node:
prev_node.right = node
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
node.left = None
prev_node = node
``````

Approach 4: can also connect things without using a prev_node:

``````    def flatten(self, root):
if not root:
return
stack = [root]
while stack:
node = stack.pop()
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
# reconnect things after children have been put on stack
node.left = None
node.right = stack[-1] if stack else None
``````

### # Code (C++)

Approach 1:

``````// Recursion.
class Solution {
private:
TreeNode* doFlattenAndReturnRight(TreeNode* root) {
if (root == NULL)
return NULL;
TreeNode *left = root->left;
TreeNode *right = root->right;
TreeNode *leftRight = doFlattenAndReturnRight(root->left);
TreeNode *rightRight = doFlattenAndReturnRight(root->right);
root->left = NULL;
if (left)
{
root->right = left;
leftRight->right = right;
}
if (rightRight)
return rightRight;
if (leftRight)
return leftRight;
return root;
}
public:
void flatten(TreeNode* root) {
doFlattenAndReturnRight(root);
}
};
``````

Approach 2:

``````// Iteration.
class Solution {
public:
void flatten(TreeNode* root) {
TreeNode *curr = root;
while (curr)
{
TreeNode *leftMostRight = curr->left;
while (leftMostRight && leftMostRight->right)
leftMostRight = leftMostRight->right;
if (leftMostRight)
{
leftMostRight->right = curr->right;
curr->right = curr->left;
curr->left = NULL;
}
curr = curr->right;
}
}
};
``````

Approach 3:

``````// Preorder simulation.
class Solution {
private:
TreeNode *prev = NULL;
public:
void flatten(TreeNode* root) {
if (root == NULL)
return;
if (prev)
{
prev->right = root;
prev->left = NULL;
}
prev = root;
TreeNode *right = root->right; // need to save the right.
flatten(root->left);
flatten(right);
}
};
``````

Approach 4:

``````// Reverse-postorder simulation.
class Solution {
private:
TreeNode *prev = NULL;
public:
void flatten(TreeNode* root) {
if (root == NULL)
return;
flatten(root->right);
flatten(root->left);
root->right = prev;
root->left = NULL;
prev = root;
}
};
``````

Approach 5:

``````// Inorder simulation.
class Solution {
private:
TreeNode *prev = NULL;
public:
void flatten(TreeNode* root) {
if (root == NULL)
return;
flatten(root->left);
TreeNode *right = root->right;
if (root->left)
{
prev->right = right; // this must be first.
root->right = root->left;
root->left = NULL;
}
prev = root;
flatten(root->right); // it's the new right (i.e., root->right).
}
};
``````