LintCode - Flatten Binary Tree to Linked List

Description: Flatten a binary tree to a fake "linked list" in pre-order traversal.

Example:

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

Analysis:

This requires a pre-order traversal, which reads the node first and then its left child, and then right-child.

Solution 1: traverse the tree and save the tree node into the list, and construct the tree again with the list.

//pseudocode for preorder traversal using recursive 
Create a list called PreOrder list

With Method preorder(Augument Root)
    If Root is initial.
        Exit.
    Save Root to PreOrder List
    Call Preorder with root’s left child.
    Call Preorder with root’s right child.

With PreOrder List
Loop at each item in the list
    Set item’s right child with the next item in the list.
    Set item’s left child to be empty

Solution 2: In place solution with recursion

Create a treenode called lastNode 
With Method Preorder (Augument Root)
    If Root is initial.
        Exit.
    If lastNode is not initial.
        Set lastNode’s right child to be Root.
        Set lastNode’s left child to be null.

    Set LastNode to be Root.

    //Root’s right child be replaced with the left child; therefore we need to save it somewhere
    Set Root’s right child to new NodeTree called Right

    Call Preorder with Root’s left child.
    Call Preorder with Right.

Solution 3: In place solution with iteration.

//Use a stack to implement pre-order traversal with iteration.

Create an empty stack object
Push root into the stack
While stack is not empty
    Pop the item from Stack
    Push item’s right child to stack
    Push item’s left child to stack

    Set item.left child to be null.    
    If stack is not empty
        Set item.right child to be the first item in the stack
    else
        Set item.right to be null