Flatten Binary Tree to Linked List

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

For example, Given

     1
    / \
   2   5
  / \   \
 3   4   6

The flattened tree should look like:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

Hints: If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.

Since the right child points to the next node of a pre-order traversal, we can use a stack to track the traversed node. O(n) space

public void flatten(TreeNode root) {
        if (root!=null) {
             Stack<TreeNode> stack = new Stack<TreeNode>();
             stack.push(root);

             while (!stack.isEmpty()) {
                 TreeNode node = stack.pop();

                 TreeNode rightNode = node.right;
                 if (rightNode!=null) {
                     stack.push(rightNode);
                 }    

                 TreeNode leftNode = node.left;
                 if (leftNode!=null) {
                     stack.push(leftNode);
                 }             

                 if (!stack.isEmpty()) {
                     node.right = stack.peek();
                 }                 
                 node.left = null;
             }
        }               
    }

In place algorithm:

        root
        /  \
     left   right

        root
           \
           left
              \
              right

the idea is to insert left into root'right subtree, then insert root's original right subtree to root's current right subtree.

KEY - append the right most node (previous node in preorder traversal) in the left sub tree to the current' right node

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

        while(root!=null) {
            if (root.left!=null) {
                TreeNode pre = root.left;
                while (pre.right!=null) {
                    pre = pre.right;
                }
                pre.right = root.right;
                root.right = root.left;
                root.left = null;
            }
            root = root.right;
        }     
    }

Recursion solution: previous visited node's left is null, right is current visiting node.

public void flatten(TreeNode root) {
        flatten(root, new TreeNode[1]);
    }

    private TreeNode flatten(TreeNode root, TreeNode[] pre) {
        if (root==null) {
            return root;
        }

        //root.right will be changed during recursion
        TreeNode rootRight = root.right;
        if (pre[0]!=null) {
            pre[0].left = null;
            pre[0].right = root;
        }
        pre[0] = root;

        flatten(root.left, pre);
        flatten(rootRight, pre);
        return root;
    }