# 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).
    }
};