dungph
BAN USERHere is a Java version with running time O(n), memory O(1) and non-recursive. The idea that makes the algorithm run without a stack (i.e. memory O(log(N))) is: if the current node have left child, go to the left but attach the current node to its right most sub-tree to come back.
Updated: Make doubly linkedlist
public static Node convertBST2LinkedList(Node root)
{
Node current=root;
int count=0;
Node front=null;
while(current!=null)
{
//if the current left is null
if(current.left==null){
// System.out.println(current.val); //print out the value
if(count==0) front=current;
count++;
//Convert here
current=current.right; //Go to right
}else{
Node temp=current.left;
while(temp.right!=null){
temp=temp.right;
}
temp.right=current;
temp=current;
current=current.left;
temp.left=null; //cut left child
}
//else
}
//Make doubly linkedlist
Node temp2=front;
if(temp2!=null){
while(temp2.right!=null){
temp2.right.left=temp2;
temp2=temp2.right;
}
}
return front;
}
@zortlord: that's true. I have just added a loop to make doubly linkedlist at the end of method. Everything is good now.
- dungph January 08, 2015