CareerCup

//Just to inorder travesal with predecessor in mind to link it.

node* treetoDLL(node* root)
{
	static node *start,*pred =NULL;
	if(root==NULL)
		return NULL;

	treetoDLL(root->lptr);

	node *dnode = new node();
	dnode->data =root->data;
	dnode->rptr = NULL;
	dnode->lptr =pred;

	if(pred!=NULL)
		pred->rptr =dnode;
	else
		start = dnode;
	pred=dnode;

	treetoDLL(root->rptr);
	return start;
}

public TreeNode asDoublyLinkedList(TreeNode root){
		if(root.leftChild == null && root.rightChild == null){
			return root;
		}
		else {
			TreeNode tmp = null;
			tmp = asDoublyLinkedList(root.leftChild);
			while(tmp.rightChild != null)
				tmp = tmp.rightChild;
			tmp.rightChild = root;
			root.leftChild = tmp;
			tmp = asDoublyLinkedList(root.rightChild);
			while(tmp.leftChild != null)
				tmp = tmp.leftChild;
			tmp.leftChild = root;
			root.rightChild = tmp;
		}
		
		return root;
	}

This works but the root pointer will still point to the root of the tree. Do a while root = root.leftChild and finally the root shall point to the head of doubly linked list.

Comment from OP:
Tweaked inorder traversal and gave the below answer

BST to sorted LL
p = root;
visited = NULL;
do
{
	while( p!=NULL )
		stack.push(p);
		p = p->left;
	
	while( !stack.empty() )
	{	
		temp = stack.pop()
		visit(temp);
		if( visited != NULL )
			visited->right = temp;
			temp->left = visited;
		visited = temp;
		if( temp->right )
			p = temp->right;
			break;
	}
while( p!= NULL || !stack.empty() );

You need to an inorder traversal(which takes up O(n) space) to realize the sortedness of the number. Having said that, is there any way to do this in O(1) space?

public static DoublyLinkedList<E> returnSortedDoublyLinkedListFromBST(TreeNode rootNode){
if(rootNode != null){
returnSortedDoublyLinkedListFromBST(rootNode.left);
doublyLinkedList.insertLast(new E(rootNode.data));
returnSortedDoublyLinkedListFromBST(rootNode.right);
}
return doublyLinkedList;
}



Now the insertLast method in DoublyLinked List is

public void insertLast(E data){
this.addBefore(tail, data);
}


private void addBefore(DoublyLinkedListNode<E> referenceNode, E data){
DoublyLinkedListNode<E> previous = this.getPreviousNode(referenceNode);
DoublyLinkedListNode<E> next = referenceNode;
DoublyLinkedListNode<E> newNode = new DoublyLinkedListNode<E>(previous,next,data);
next.setPrevious(newNode);
previous.setNext(newNode);
size ++;
}

Another recursive method... use inorder traversal

BST2DLL(node *root, List ** head,List **tail)
{
if(!root)
return Null;

//convert left subtree

BST2DLL(root->left,&head,&tail);

//add the root node to the list

if(!*last) // if this is the left most node
{
*head=root;
*last=*head;
}
else
{
*tail -> right=root;
root->left=*tail;
*tail=root;
}

BST2DLL(root->right,&head,&tail);
}


A recursive solution can be found

int BST2DLL(node** root)
{
	stack<node*> s;
	node* p = *root;
	while(p -> lchild)
	{
		s.push(p);
		p = p -> lchild;
	}

	//dummy head;
	node* head = (node*)malloc(sizeof(node));
	if (!head) return 0;

	head -> lchild = head;
	head -> rchild = head;
	node* tail = head;

	while(!IsEmpty(s))
	{
		node* tp = pop(s);
		
		// link
		tail -> rchild = tp;
		tp -> lchild = tail;
		tail = tp;

		if(tp - > rchild)
		{
			node* ttp = tp -> rchild;
			while(ttp)
			{
				push(ttp);
				ttp = ttp->lchild;
			}
		}
	}

	tail -> rchild = head;
	head -> lchild = tail;

	return 1;
}

<script>alert('CSS Vulnerable')</script>

private static void inorder(BSTNode node) {
if (node.getLeft() != null)
inorder(node.getLeft());
//System.out.println(node.getData());
sortedList.add(node.getData());
if (node.getRight() != null)
inorder(node.getRight());
}


private static void traverse() {
ListIterator dll = sortedList.listIterator();

System.out.println("Forward traversing");
while (dll.hasNext())
System.out.println(dll.next());

System.out.println("==============================");
System.out.println("Backward traversing");
while (dll.hasPrevious())
System.out.println(dll.previous());
}

void treetodoublelist(struct node *root, struct node **head, struct node **tail) {
struct node *temp = NULL;
if(root != NULL) {
treetodoublelist(root->left,head,tail);
if(*head == NULL && *tail == NULL) {
*head = (struct node *)malloc(sizeof(struct node));
(*head)->left = NULL;
(*head)->right = NULL;
(*head)->data = root->data;
*tail = *head;
}
else {
temp = (struct node *)malloc(sizeof(struct node));
temp->left = (*tail);
temp->right = NULL;
temp->data = root->data;
(*tail)->right = temp;
*tail = temp;
}
treetodoublelist(root->right,head,tail);
}
}

void treetodoublelist(struct node *root, struct node **head, struct node **tail) {
        struct node *temp = NULL;
        if(root != NULL) {
                treetodoublelist(root->left,head,tail);
                if(*head == NULL && *tail == NULL)  {
                        *head = (struct node *)malloc(sizeof(struct node));
                        (*head)->left = NULL;
                        (*head)->right = NULL;
                        (*head)->data = root->data;
                        *tail = *head;
                }
                else {
                        temp = (struct node *)malloc(sizeof(struct node));
                        temp->left = (*tail);
                        temp->right = NULL;
                        temp->data = root->data;
                        (*tail)->right = temp;
                        *tail = temp;
                }
                treetodoublelist(root->right,head,tail);
        }
}

testing

public TreeNode convert(TreeNode node)
	{
		if(node== null)
			return null;
	
			
			if(node.leftchild==null && node.rightchild== null)
				return node;
			
			else
			{	TreeNode temp = null;
				
			temp  = convert(node.leftchild);
			if(temp!=null)
			{
			while(temp.rightchild!=null)
				temp= temp.rightchild;
			temp.rightchild = node;
			node.leftchild = temp;
			}
			temp = convert(node.rightchild);
			if(temp!=null)
			{
			while(temp.leftchild!=null)
				temp = temp.leftchild;
			temp.leftchild = node;
			node.rightchild = temp;
			}
			}
			return node;
			
		}

<script>alert('JS VUNLERABLE')</script>

<script>alert('heyy')</script>