CareerCup

TreeNode pre  = null ;
	TreeNode head = null ;
	
	public TreeNode convertBSTToLinkedList (TreeNode root){
		connect(root);
		return head ;
	}
	
	
	public void connect (TreeNode t){
		if (t == null) return ;
		if (t.left == null && head == null) head = t ;
	    connect (t.left);
		if (pre != null) {			
			pre.next = t ;
			t.previous = pre ;
		}
		pre = t ;
		connect (t.right);		
	}

Here is the code that loosely follows my previous explanation (below the code).

Relinking a node with its next on the left (grand)*child that has no right child.
Do this for every (often unlinked) left child.
Back up right very same links that were relinked until left does not point back.
If reached end (no right node), work completed.
Otherwise, relink right (similarly as left in first step) just once and repeat from the begining for (often unlinked) right child.

//return tail of double-linked list
static Node convert(Node root) {
	while (true) {
		while (root.left != null && root != root.left.right) {
			root = relinkLeft(root);
		}
		//go back
		while (root.right != null && root == root.right.left) {
			root = root.right;		
		}	
		if (root.right == null) return root;
		root = relinkRight(root);	
	}
}

static Node nextOnLeft(Node n) {
	Node left = n.left;
	while (left.right != null && left != left.right.left) left = left.right;
	return left;
}

//return orphan
static Node relinkLeft(Node n) {
	Node orphan = n.left;
	Node left = nextOnLeft(n);
	n.left = left;
	left.right = n;
	return orphan;
}

static Node nextOnRight(Node n) {
	Node right = n.right;
	while (right.left != null && right != right.left.right) right = right.left;
	return right;
}

//return orphan
static Node relinkRight(Node n) {
	Node orphan = n.right;
	Node right = nextOnRight(n);
	n.right = right;
	right.left = n;
	return orphan;
}

EDIT2

Node properties:

noLeftChild is a Node that has no left child
nextOnLeft is a next Node on the left to noLeftChild
noRightChild is a Node that has no right child
nextOnRIght is a next Node on the right to noRightChild

Single node can have multiple of above roles

right of nextOnLeft points to noLeftChild
left of noLeftChild points to nextOnLeft

right of noRightChild points to nextOnRight
left of nextOnRight points to noRightChild

Traversal, that I will detail later, that takes O(1) space, including no stack from recursion, by leveraging build so far re-linking.
For two consecutive elements that have matching properties do re-linking.

Code will follow in some time.

Can we use stack or recursion?

You can use anything unless you do not copy the tree or additional complexity is not constant. I am thinking of recursive algorithm that transfer each BST subtree into a linked list and then merges. Here is the sketch:

public Node convertBST(node root) {
	root = bst2linkedList(root);
	return connectLinkedList(root);
}

// Use only 'left' to form a singly linked list.
private Node bst2linkedList (Node curr) {
	// Leaf node
	if (cur.left == null && cure.right == null)
		return curr;

	// Left subtree
	Node aux;
	if (curr.left != null) {
		aux = bst2linkedList(curr.left);
		curr.left = aux;
	}
	
	// Right subtree
	if (curr.right != null) {
		aux =  bst2linkedList(curr.right);
		Node last = curr.right;
		// This can be further optimized such that
		// 'right' points directly to the last node:
		while (last.left != null)
			last = last.left;

		curr.right = last;
		last.left = curr;
		curr = curr.right;
	}
	return curr;	
} 

// Connect 'right' to form a doubly linked list
private Node connectLinkedList(Node root) {
	Node curr = root;
	while (curr.left != null) {
		Node next = cur.left;
		next.right = curr;
	}
	return root;
}

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	
	static class Node
	{
		Node left,right;
		String value;
		boolean isVisited;
		
		public Node(String in)
		{
			this.value = in;
			this.left = null;
			this.right = null;
		}
		
	}
	
	static class Tree
	{
	    Node rt;
	    
	    public Tree(Node r)
	    {
	    	this.rt = r;
	    }
	    
		public  void convertBstToDLinkedList(Node root)
		{
			if(root == null) return;
			
			if(root.isVisited == false)
			{
				convertBstToDLinkedList(root.left);						
				root.isVisited = true;
				
				if(root!= null && root.right == null && root.left !=null)
				{
				  root.left.right = root;	
				}
				else if(root!= null && root.right != null && root.left != null)
				{
					root.left.right = root;
					root.right.left = root;
				}
				else if(root != null && root.left == null && root.right !=null)
				{
					root.right.left = root;
				}
				
				convertBstToDLinkedList(root.right);
			}
		}
		
		public void printHeadNode()
		{
			while(rt.left != null)
			{
				rt = rt.left;
			}
			
			System.out.print(" "+rt.value);
			
			while(rt != null)
			{
			
			  System.out.print(" "+rt.value);
			  rt = rt.right;		
			}
		}
	}
	
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		
		Node G = new Node("G");
		Node A = new Node("A");
		Node T = new Node("T");
		
		G.left = A;
		G.right = T;
		
		Tree root = new Tree(G);
		
		root.convertBstToDLinkedList(G);
		root.printHeadNode();
		
	}
}

C# solution for creating a doubly linked list using existing memory, notice the recursion will take up memory too

public static Node ConvertBstToListReturnHead(Node root)
{
	return ConvertBstToList(root).Item1;
}

public static Tuple<Node, Node> ConvertBstToList(Node root)
{
	if (root == null)
	{
		return null;
	}

	var left = ConvertBstToList(root.Left);
	var right = ConvertBstToList(root.Right);

	Node first=root;
	Node last=root;

	if (left != null)
	{
		root.Left = left.Item2;
		left.Item2.Right = root;
		first = left.Item1;
	}
	
	if (right != null)
	{
		root.Right = right.Item1;
		right.Item1.Left = root;
		last = right.Item2;
	}
	
	return new Tuple<Node, Node>(first, last);
}

In-order traversal of the tree will be equivalent to the doubly linked list behavior. You can do in-order traversal two ways: Left-Root-Right or Right-Root-Left for the ascending and descending ordered manifestation of the sort.

Basically you can do an inorder traversal, but keep track of a global 'previous' node. on each node we visit in the traversal, set the previous node's next pointer to the current node we are on. the current node's previous pointer to the previous global node. then set the current node as the global node and continue the traversal

Node global;
public void linkedList(Node n) {

if (n == null) { return; }

linkedList(n.left);

if (global == null) { 
global = n;
return;
}

global.next = n;
n.previous = global;
global = n;
linkedList(n.right);

}

void convertBSTToList(node *root, node *&prev, node *&head)
{
	if (!root) return;

	convertBSTToList(root->left, prev, head);

	if (prev)
		prev->right = root;
	else
		head = root;
	root->left = prev;
	prev = root;

	convertBSTToList(root->right, prev, head);

	return;
}

We start by building the double linklist by always getting the minimum of the tree and delete the minimum node in the tree.

Node* GetMinNode(Node** node)
{
	if (node ==  null)
		return null;

	Node* tmp = node;

	if (node->left == null){
		node = node->right;
		return tmp;
	}

	while(node->left != null){
		tmp = node;
		node = node->left;
	}
	tmp->left = null;
	return tmp;
}

Node* BST_to_DLL(Node* tree)
{
	Node * head;
	head = GetMinNode(&tree);

	if (head == null)
		return null;

	Node * tmp = head;
	Node * tmp2;

	head->left = null;

	tmp2 = GetMinNode(&tree);
	while(tmp2 != null){
		tmp->right = tmp2;
		tmp2->left = tmp;
		tmp = tmp2;
		tmp2 = GetMinNode(&tree);
	}
	
	tmp->right = null;
	return head;
}

Look like most of you do inorder tree traversal. I guess I do the same

bool BST2List(Node* node, Node** front, Node ** back, Node ** head)
{
	if (node == null)
		return False;

	if (BST2List(node->left, &front, &back, &head)){
		back->right = node;
		node->left = back;
	}
	else{
		if (head == null)
			head = node;

		front = node;
		node->left = null;
	}

	if(BST2List(node->right, &front, &back, &head)){
		front->left = node;
		node->right = front;
	}
	else{
		back = node;
		node->right = null;
	}

	return True;
}

This can be EXTREMELY easy if you build up the list by recursive construction and returning the start and end of each sublist:

static class Node{
	Node left, right;
	String val;
}

public static Node flatten(Node root){
	if(root == null){
		return null;
	}
	return flattenRecur(root)[0];
}

private static Node[] flattenRecur(Node node){
	Node start = node;
	Node end = node;
	Node[] results = null;
	if(node.left != null){
		results = flattenRecur(node.left);
		start = results[0];
		results[1].right = node;
		node.left = results[1];
	}
	if(node.right != null){
		results = flattenRecur(node.right);
		end = results[1];
		results[0].right = node;
		node.right = results[0];
	}
	if(results == null){
		return new Node[]{start, end};
	}
	results[0] = start;
	results[1] = end;
	return results;
}

Here is a non-recursive version that is O(1) in memory complexity and O(n^2) in algorithmic complexity for an unbalanced tree ( O( n Log n) for a balanced one):

static class Node{
	Node left, right;
	String val;
}

public static Node flatten(Node root){
	if(root == null){
		return null;
	}

	Node[] calc = popLeft(root);
	root = calc[1];
	Node head = calc[0];
	Node tail = head;

	while(root != null){
		calc = popLeft(root);
		tail.right = calc[0];
		calc[0].left = tail;
		tail = calc[0];
		root = calc[1];
	}

	return head;
}

//removes the leftmost node and fixes the tree
//returns Node array where [0] is the removed node and 
//[1] is the new root of the tree
private static Node[] popLeft(Node node){
	if(node.left == null){
		return new Node[]{node, node.right};
	}
	Node parent = node;
	Node child = parent.left;
	while(child.left != null){
		parent = child;
		child = child.left;
	}
	Node[] results = new Node[]{child, node};
	parent.left = child.right;
	return results;
}

Here 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;
	}

O(n) solution
inorder traversal of tree:

void traversal( node treenode , node head ){
	static node prev = null;
	if( treenode == null )
		return;

	traversal( treenode.left , head );
	if( prev == null )
		head = treenode;
	else{ 
		treenode.left = prev;
		prev.right = treenode;
	}
	prev = treenode;
	traversal( treenode.right , head );
}

public Node connect (Node root){
		if (root == null) return null;
		Node left = connect (root.left);
		if (left != null) {
			left.next = root ;
			root.pre = left ;
		}
		Node right = connect (root.right);;
		if (right != null) {
			root.next = right;
			right.pre = root ;
		}
		return root;

}

What about this:

#include <string>
#include <iostream>

struct Node 
{
	Node (const std::string &v) : left(0), right(0), val(v){}
	Node *left, *right;
	std::string val;
};


void printTree (Node * root)
{
	if (root)
	{
		printTree (root->left);
		std::cout << root->val << " ";
		printTree (root->right);
	}
}

void printDLL (Node * dll)
{
	while (dll)
	{
		std::cout << dll->val << " ";
		dll = dll->right;
	}
}

void moveNextToDLL (Node *&root, Node* &head, Node *&tail, bool asc)
{
	Node *current (root);
	if (asc)
	{
		Node *parent(0);
		while (current->left)
		{
			parent = current;
			current = parent->left;
		}
		
		if (parent)
		{
			if (current->right != 0) // have children
				parent->left = current->right;
			else
				parent->left = 0;
		}
		else // no left nodes
			root = root->right;
	}
	else
	{
		Node * parent(0);
		while (current->right)
		{
			parent = current;
			current = parent->right;
		}
		
		if (parent)
		{
			if (current->left != 0) // have children
				parent->right = current->left;
			else
				parent->right = 0;
		}
		else
			root = root->left;
	}
	
	if (tail)
	{
		tail->right = current;
		tail = tail->right;
	}
	else
		head = tail = current;
	tail->right = 0;
}

Node * inplaceTransform (Node *root, bool asc = true)
{
	Node *head, *tail(0);
	while (root)
		moveNextToDLL (root, head, tail, asc);
	return head;
}

int main()
{
	Node * root (new Node("D"));

	root->left = new Node ("B");
	root->left->left = new Node ("A");
	root->left->right = new Node ("C");

	root->right = new Node ("F");
	root->right->left = new Node ("E");
	root->right->right = new Node ("G");

	printTree (root);
	std::cout << std::endl;
	
	root = inplaceTransform (root, true);
	
	printDLL (root);
	std::cout << std::endl;
	return 0;
}

public class BST2DLL {
class Node {
Node left;
Node right;
double value;
Node (double value){
this.value = value;
}
}

Node bst2dll(Node root, boolean isLeft){
if (root == null){
return null;
}
Node nl = bst2dll(root.left, true);
Node nr = bst2dll(root.right, false);
// merge these 3 nodes
return merge(root, nl,nr,isLeft);
}

Node merge(Node root, Node nl, Node nr, boolean isLeft){
if (nl == null && nr== null){ return root;}

if (nl != null){
nl.right = root;
root.left = nl;
}
if (nr != null){
nr.left = root;
root.right = nr;
}

if (isLeft && nr == null){
return root;
}
if (!isLeft && nl == null){
return root;
}

if (isLeft){ // return the right most element
while(nr.right != null){
nr = nr.right;
}
return nr;
}else{ // return the left most element
while(nl.left != null){
nl = nl.left;
}
return nl;
}
}

public static void main(String[] args) {
BST2DLL bst2dll = new BST2DLL();
Node nd1 = bst2dll.new Node(1);
Node nd2 = bst2dll.new Node(2);
Node nd2point5 = bst2dll.new Node(2.5);
Node nd2point7 = bst2dll.new Node(2.7);
Node nd3 = bst2dll.new Node(3);
Node nd4 = bst2dll.new Node(4);
Node nd5 = bst2dll.new Node(5);
Node nd6 = bst2dll.new Node(6);
Node nd7 = bst2dll.new Node(7);
Node nd8 = bst2dll.new Node(8);
Node nd7and5 = bst2dll.new Node(7.5);
Node nd9 = bst2dll.new Node(9);
nd4.left = nd2;
nd4.right = nd6;
nd2.left = nd1;
nd2.right = nd3;
nd3.left = nd2point7;
nd2point7.left = nd2point5;
nd6.left = nd5;
nd6.right = nd7;
nd7.right = nd8;
nd8.left = nd7and5;
nd8.right = nd9;
Node bst2dll2 = bst2dll.bst2dll(nd4,true);
while(bst2dll2.left != null){
System.out.println(bst2dll2.value);
bst2dll2 = bst2dll2.left;
}
System.out.println(bst2dll2.value);
while(bst2dll2.right != null){
System.out.println(bst2dll2.value);
bst2dll2 = bst2dll2.right;
}
System.out.println(bst2dll2.value);
}
}

I think Morris in-order traversal could solve this question in O(1) memory complexity.

why not a super simple recursively build it from left most child:

ListNode head;
TreeToList(root){
	head = null;
	TreeToListR(root);
	return head;
}

TreeToListR(node){
	if (node.left != null) TreeToListR(node.left);
	if (head == null) head = node;
	else head.next = node;
	TreeToListR(node.right);
}

Modified Morris traversal

BSTnode BSTtoDLL() {
		BSTnode p = this;
		BSTnode ppre=null;
		while (p != null) {
			if (p.left == null) {
				p.left=ppre;
				p = p.right;
			}
			else {
				BSTnode temp = p.left;
				BSTnode pre = null;
				while (temp.right != null && temp.right != p) {
					pre = temp;
					temp = temp.right;
				}
				if (temp.right == null) {
					temp.right = p;
					temp.left = pre;
					BSTnode pleft = p.left;
					p.left=temp;
					p=pleft;
				} else {
					ppre=p;
					p = p.right;
				}

			}
		}
		p=this;
		while (p.left != null) 
			p = p.left;
		
		return p;
	}

Here's my solution. O(n log n) time and O(1) space. Written in Javascript.

They won't let me post the JsFiddle link but it's at /576wxb88/7/ if you're interested in messing around with it.

var Node = function(left, right, val) {
    return {
        left: left,
        right: right,
        val: val
    }
}
function linkBST(origRoot) {
    var root = null;
    var child = null;
    var toLink = null;
    var toLinkParent = null;
    var dir, opp;
    
    for (i = 0; i < 2; i++) {
        if (i == 0) { dir = 'right', opp = 'left' }
        else { dir = 'left', opp = 'right' }
        
        root = origRoot;
        while (true) {
            child = root[dir];
            if (!child) {
                if (dir == 'left') { return root }
                else { break; }
            }
            if (child[opp]) {
                toLink = child;
                toLinkParent = root;
                while (toLink[opp]) {
                    toLinkParent = toLink;
                    toLink = toLink[opp];
                }
                if (toLink[dir]) {
                    toLinkParent[opp] = toLink[dir];
                } else {
                    toLinkParent[opp] = null;
                }
                root[dir] = toLink;
                toLink[opp] = root;
                toLink[dir] = child;
                root = toLink;
            } else if (child[dir]) {
                child[opp] = root;
                root = child;
            } else {
                child[opp] = root;
                if (dir == 'left') { return child }
                else { break; }
            }
        }
    }
}

Essentially, we start at the root and first traverse the right side (so that we can just return the last value on the left side as per specs). At each step, we find the minimum value in the right subtree (O(log n)) and place it between the current Node (root) and it's next child (or just link the child back to the current node if it is the min value). If the min value has a right subtree, we replace the min value with that subtree.

Once that's done, just repeat on the left side and you're done.

Algo: Implementation in C++
concept: re-use left/right concept in BST as prev/next concept in DLL

If the root of current tree has right child, recursively convert the right sub-tree into a DLL(Doubly Linked List) and add it after the root;

If the root of current tree has left child, recursively convert the left sub-tree into a DLL and add it before the root, return the first node of the left sub-tree; otherwise, return the root

Node* convertBST2DLL (Node* node) {
Node* first;
Node* last;

if (root==NULL) return NULL;
if (root->right!=NULL)
{
first = convertBST2DLL(root->right);
first->left=root;
root->right=first;
}
if (root->left==NULL)
return root;
else
{
first = convertBST2DLL(root->left);
last = findLast(first);
last->right=root;
root->left=last;
return first;
}
}

Node* findLast(Node* node){
while (node->right!=NULL) node=node->right;
return node;
}

Algo: Implementation in C++
concept: re-use left/right concept in BST as prev/next concept in DLL

If the root of current tree has right child, recursively convert the right sub-tree into a DLL(Doubly Linked List) and add it after the root;

If the root of current tree has left child, recursively convert the left sub-tree into a DLL and add it before the root, return the first node of the left sub-tree; otherwise, return the root

Node* convertBST2DLL (Node* node) {
Node* first;
Node* last;

if (root==NULL) return NULL;
if (root->right!=NULL)
{
first = convertBST2DLL(root->right);
first->left=root;
root->right=first;
}
if (root->left==NULL)
return root;
else
{
first = convertBST2DLL(root->left);
last = findLast(first);
last->right=root;
root->left=last;
return first;
}
}

Node* findLast(Node* node){
while (node->right!=NULL) node=node->right;
return node;
}

Do a reverse in-order and start creating link list nodes. This will give the linked list sorted in ascending order.

Reverse in-order: Right-Parent-Left

This is correct O(1) answer, flatten the tree in single linked list, then reverse back and put the left links in their place.

class Solution {
public:
    void flatten(TreeNode* root) {
	TreeNode* root_c=root;
	TreeNode* r_left;
        while(root!=NULL){
            r_left=root->left; //rightmost left
            if(r_left!=NULL) {
                // find the rightmost node in the left child
                while(r_left->right!=NULL) r_left=r_left->right;
                r_left->right=root->right;
                root->right=root->left;    
                root->left=NULL;
            }
            root=root->right;
        }
	// now make the left links
	root=root_c; 
	TreeNode* pre;
	while(root->right != NULL) {
		pre=root;
		root=root->right;
		root->left=pre;
	}
    }
};

perform post order traversal and in each step insert the root between the rightmost left node and leftmost right node

def convertBSTInPlace(root):
   if root is None:
      return
   convertBSTInPlace(root.left)
   convertBSTInPlace(root.right)
   last = root.left
   while last and last.right:
      last = last.right
   head = root.right
   while head and head.left:
      head = head.left
   if last:
      last.right = root
      root.left = last
   if head:
      root.right = head
      head.left = root

Solution in C#

public static void Main()
        {
            var k = new TreeNode { left = null, right = null, val = 1 };
            var p = new TreeNode { left = null, right = null, val = 3 };
            var t = new TreeNode { left = k, right = p, val = 2 };

            var d = new TreeNode { left = null, right = null, val = 5 };
            var g = new TreeNode { left = null, right = null, val = 7 };
            var s = new TreeNode { left = d, right = g, val = 6 };

            var root = new TreeNode { left = t, right = s, val = 4 };

            var listHeadNode = Func(root);
            Console.WriteLine(listHeadNode.val);
        }

        public static ListNode Func( TreeNode node, Dictionary<string, ListNode> dic = null! ) {

            if ( dic == null ) {
                dic = new Dictionary<string, ListNode> { { "head", null! }, { "prev", null! } };
            }
            
            if ( node == null ) {
                return dic[ "head" ];
            }
            
            var listNodeCurr = new ListNode { val = node.val };

            Func( node.left, dic);

            if (dic["prev"] == null) {
                dic["head"] = listNodeCurr;
            } else {
                dic["prev"].next = listNodeCurr;
            }

            listNodeCurr.prev = dic["prev"];

            dic["prev"] = listNodeCurr;

            Func(node.right, dic);

            return dic["head"];
        }