Flatten a Binary Tree

Given a tree like
                   root
          0.left           0.right
1.left    1.right    2.left    2.right
flatten it as a list in place, like
                                      root
                                0.left
                        1.left
                1.right
        0.right
    2.left
2.right

Codes:

package tree;

public class TreeNode {
String val;
TreeNode left;
TreeNode right;

public TreeNode(String value){
this.val=value;
}
}

package tree;

import java.util.Stack;

public class FlatternATree {

static TreeNode aTree = new TreeNode("root");

/**

* @param args

*/

public static void main(String[] args) {

prepareATree();

System.out.println(aTree);

flattenTree(aTree);

System.out.println(aTree);

}

static void prepareATree(){

TreeNode l = new TreeNode("0.left");

TreeNode r = new TreeNode("0.right");

aTree.left = l;

aTree.right = r;

l.left = new TreeNode("1.left");

l.right = new TreeNode("1.right");

r.left = new TreeNode("2.left");

r.right = new TreeNode("2.right");

}

static void flattenTree(TreeNode root){

TreeNode p;

Stack s = new Stack();

p = root;

while(p!=null){

if (p.right!=null){

s.push(p.right);

//right node is now pointed by stack, remove the linkage from its parent node

p.right = null;

}

if(p.left==null){

if(!s.empty()){

p.left = s.pop();

}

else

break;

}

p=p.left;

}

}

}