Pre-Order Flatten A Binary Tree to Linked List

To do it iteratively is little bit tricky, since when we do down to the left of tree, we need to remember the way to go back to right.

The idea is to use a stack to store the right child when we go to left.

Here is the code:

public static void FlattenABinaryTreetoLinkedList(Node root){

Stack<Node> s = new Stack<Node>();

Node c = root;

while(!s.isEmpty()||c!=null){

if(c.left!=null){//keep on going left

if(c.right!=null)//remember the right child

s.push(c.right);

c.right = c.left;

c.left = null;

c = c.right;

}

else{//reach the far left, now we need to go right

Node n = s.pop();

c.right = n;

c = n;

}

}

}