CareerCup

node * from_list(node *N)
{
if((N==Null)
return(NULL);
L1=N;
if(N->left!= NULL)
{
L1=from_list(N->left);
T=last(L1);
T->right=N;
}
if(N->right!= NULL)
N->Right=from_list(N->right);
return(L1);
}


node *Last (node *N)
{
while (N-right!=NULL)
N=N->right;
return(N);
}

getSortedList(root, head, tail)
	
		if root = null
			return
		
		if root.left != null
			getSortedList(root.left, head, tail)
		
		if head = null
			head <- root
		if tail = null
			tail <- head
		else 
			tail.next <- root
			
		if root.right != null
			getSortedList(root.right, head, tail)
		
		return

next is the pointer to right child.
prev is the pointer to left child.

BST2DLL(root,start)
{
	if(root)
	{
		BST2DLL(root->left);
		if(!start)
			start=root;
		else
		{
			prevNode->next=root;
			root->prev=prevNode;
		}
		prevNode=root;

		BST2DLL(root->right);
	}
}

prevNode is static here.
After the execution of the function is over, start will be pointing to the head of the DLL.

public static List<Node> convertToSLL(Node node, Node head, Node tail)
	{
		ArrayList<Node> list  = new ArrayList<Node>();
		list.add(head);
		list.add(tail);
		if (node == null)
		{
			return list;
		}
		
		if (node.getLeft() != null)
		{
			list  = (ArrayList<Node>) convertToSLL(node.getLeft(), head, tail);
			head = list.get(0);
			tail = list.get(1);
		}
		
		if (head == null)
		{
			head = node;
		}
		else
		{
			Node temp = head;
			
			while (temp.getRight() != null && temp != tail)
			{
				temp = temp.getRight();
			}
			
			if (!temp.equals(node))
			{
				temp.setRight(node);
				tail = node;
			}
			else
			{
				tail = temp;
			}
		}
		
		if (node.getRight() != null)
		{
			list  = (ArrayList<Node>) convertToSLL(node.getRight(), head, tail);
			head = list.get(0);
			tail = list.get(1);
		}
		
		list.set(0, head);
		list.set(1, tail);
		return list;
	}

Node head = null, lastNode = null;

public void bstToList(Node current){
        if(current == null)
            return;
	if(current.getLeft()!=null)
		bstToList(current.getLeft());
	Node right = current.getRight();
	if(head == null){
		head = current;
	}
        if(lastNode != null)
	        lastNode.setRight(current);
	lastNode = current;
        lastNode.setRight(null);
	if(right!=null)
		bstToList(right);
}

The steps are quite simple,

1. Find the in-order predecessor & successor of the current node
2. Recurse into each of the child
3. Once done with childs, point inorder predecessor next to current node and currentnode's next to inordersucessor

/**
* Returns the head of the transformed linked list
*/
public BinaryTreeNode convertBSTIntoSortedLL(BinaryTreeNode root){
	convertBSTIntoSortedLLHelper(root);
	return getLeftMostChild(root);
}
/**
* The actual meat of the algorithm
*/
private void convertBSTIntoSortedLLHelper(BinaryTreeNode root){
	if(root == null){
		return;
	}
	// Get the inorder successor and predecessors
	BinaryTreeNode inorderPredesessor = null;
	BinaryTreeNode inorderSuccessor = null;
	if(root.getLeft() != null){
		inorderPredesessor = getRightMostChild(root.getLeft());
	}
	if (root.getRight() != null){
		inorderSuccessor = getLeftMostChild(root.getRight());
	}
	// Recurse into both left and right subtree
	convertBSTIntoSortedLLHelper(root.getLeft());
	convertBSTIntoSortedLLHelper(root.getRight());
	// Set the references properly
	if(inorderPredesessor != null){
		inorderPredesessor.setRight(root);
	}
	if(inorderSuccessor != null){
		root.setRight(inorderSuccessor);
	}
}

private BinaryTreeNode getRightMostChild(BinaryTreeNode node){
	while(node.getRight() != null){
		node = node.getRight();
	}
	return node;
}

private BinaryTreeNode getLeftMostChild(BinaryTreeNode node){
	while(node.getLeft() != null){
		node = node.getLeft();
	}
	return node;
}

yes dude, I wrongly calculated it, the complexity is going to be of the order of O(nlogn) in the second case, but just one minute edge case is missing that the last node's right pointer should be pointing to null.

public Node bstToList(Node current, int flag){
if(current == null){
return null;
}
if(current.left == null && current.right == null){
return current;
}
Node ln = bstToList(current.left, 0);
Node rn = bstToList(current.right, 1);
current.left = ln;
current.right = rn;
if(ln != null ){
ln.right = current;
}
if(rn != null){
rn.left = current;
}
if(flag == 0){
while(current.right != null){
current = current.right;
}
return current;
} else if(flag == 1){
while(current.left != null){
current = current.left;
}
return current;
}
return null;
}

Call the function like this...
Node head = bst.bstToList(root, 1);
1 for left and 0 for right.
----------------------------------------

public Node bstToList(Node current, int flag){
if(current == null){
return null;
}
if(current.left == null && current.right == null){
return current;
}
Node ln = bstToList(current.left, 0);
Node rn = bstToList(current.right, 1);
current.left = ln;
current.right = rn;
if(ln != null ){
ln.right = current;
}
if(rn != null){
rn.left = current;
}
if(flag == 0){
while(current.right != null){
current = current.right;
}
return current;
} else if(flag == 1){
while(current.left != null){
current = current.left;
}
return current;
}
return null;
}

Use iterative inorder traversal and When poping enqueue them into a Q immediately see if size of Q ==2 if so dequeue and make right pointer of the dqueued element point to next element in Q.

Ashok,

What you have done is correct.
I'll just break it down to my understanding of the problem here.
We need to only change the right links of the nodes. As mentioned, right links need to point to the inorder successor of the current node.
The inorder successor can be one of the following:
(a) Father of the node itself : When we're traversing a left sub tree of a given root.
(b) Some ancestor of the root. In this case, the node is the rightmost member of a right sub tree of a given root.
(c) The left most child of the right subtree of the given node.

To that end, I present the code below:
{
NODE * convertToSortedList(NODE * root, NODE * ancestor) {
NODE * tL, *tR;
if ( root == NULL)
return NULL;
tL = convertToSortedList(root->left, root); // takes care of case (a) above.
tR = convertToSortedList(root->right, ancestor);
if(tr == NULL) {
if(root -> info < ancestor -> info )
root - > right = ancestor;
return root;
// Here, if the root is part of some left sub tree, ancestor will be the father.
// If its in some right sub tree, ancestor will be ancestor of its father.
}
else {
//This means, that the function has returned the inorder successor of the
//current node from the right sub tree.
root -> right = tR;
if (tL != NULL)
return tL; // tL is the inorder successor. Leftmost of the left subtree
else
return root;
}
}
}
Usage: call convertToSortedList (root,root) and you get the head of the sorted linked list.

Let me know your thoughts. Thanks

BST2LinkList(Node *pRoot)
{
	Node *nextNode = NULL;
	Node *currNode = pRoot;
	Node newRootNode = pRoot;
	while(pRoot)
	{
		if(currNode -> right == NULL)
		{
			currNode -> right = nextNode;
			nextNode = currNode;
		}
		else
		{ 
			BST2LinkList(currNode -> right); 
			currNode -> right = nextNode;
			nextNode = currNode;
		}
		
		if( currNode -> left != NULL )
		{
			BST2LinkList(currNode -> left);
			newRootNode = currNode -> left;
			currNode -> left = NULL;
			
		}
	}
	return newRootNode;
}

void BstToLinkedList()
       {
               Node* root = Root;
               Root = NULL;
               bool flag = false;
               Node* prev = Root;
ONE:
               while(root->left != NULL)
               {
                       Node* temp = root->left;

                       while(temp->right!=NULL)
                               temp = temp->right;

                       temp->right = root;
                       temp = root->left;
                       root->left = NULL;
                       root = temp;
               }
               if(flag==false)
               {
                       Root = root;
                       flag = true;
               }
               else
                       prev->right = root;

               while(root!= NULL && root->left==NULL)
               {
                       prev = root;
                       root = root->right;
               }
               if(root != NULL)
                       goto ONE;
       }

Node* RotateRight( Node* Root )
       {
               Node* q = Root->left;
               Node* hold = q->right;
               q->right = Root;
               Root->left = hold;
               return q;
       }

       //returns the head of the linked list
       Node* BstToLinkedList(Node* Root)
       {
               Node temp;
               Node* prev = &temp;

               while(Root!=NULL)
               {
                       while(Root->left != NULL)
                       {
                               Root = RotateRight(Root);
                       }
                       prev->right = Root;

                       prev = Root;
                       Root = Root->right;
               }
               return temp.right;
       }

inorder(struct tree*t)
{
if(t==NULL)return;
inorder(t->left);
printf("%d",t->data);
inorder(t->right);
}

i think this just works perfect,, n simple too!!

while(root->left != NULL){
temp = root;
delete(root);
insert(root->left,temp);
}

public class Tree2SLL{
public Node root;

private class Node{
public int val;
public Node right;
public Node left;
}
//Pass null to successor when calling the api, as the lastNOde.right will be null in the list
public Node TreetoSLL(Node root, Node successor){
if(root.left == null && root.right == null) return null;
if(root.right != null) TreetoSLL(root.right,successor);
root.right = successor;
successor = root;
if(root.left != null) TreetoSLL(root.left,successor);
return successor;
}
}

Very Easy question ,
Algorithm:
- given a node in a bst, the rightmost child of the given node should point to the parent of the current node.
- the left child of the current node is to point to the parent(using the right link), and make left like of the curreent node equals to null.
- do this recursively for all nodes

NOTE : the trick is to parse the tree from its leftmost end (DFS)

node* CreateList(node *t)
{
if(t)
{
CreateList(t->left);

	if(t->left)
	{
			node* temp=FindRightMax(t->left);
			temp->right=t;
			t->left=NULL;
	}
CreateList(t->right);
}

node* FindRightMax(node *t)
{
if(t)
{
	while(t->right)
			t=t->right;
}
return t;
}

http :// cslibrary .stanford. edu/ 109 /TreeListRecursion.pdf

public static void main(String[] args) {

	BinaryTreeNode n2 = new BinaryTreeNode(null, null, 2);
	BinaryTreeNode n6 = new BinaryTreeNode(null, null, 6);
	BinaryTreeNode n5 = new BinaryTreeNode(n2, n6, 5);

	BinaryTreeNode n12 = new BinaryTreeNode(null, null, 12);
	BinaryTreeNode n14 = new BinaryTreeNode(null, null, 14);
	BinaryTreeNode n13 = new BinaryTreeNode(n12, n14, 13);

	BinaryTreeNode n20 = new BinaryTreeNode(null, null, 20);
	BinaryTreeNode n15 = new BinaryTreeNode(n13, n20, 15);

	BinaryTreeNode root = new BinaryTreeNode(n5, n15, 10);
	BinaryTreeNode head = treeToList(root);
	while (head != null) {
	    System.out.print(head.value + " ");
	    head = head.next;
	}
    }

    public static BinaryTreeNode treeToList(BinaryTreeNode root) {

	if (root == null) {
	    return null;
	}

	BinaryTreeNode right = treeToList(root.right);
	BinaryTreeNode listNode = new BinaryTreeNode(null, null, root.value);
	listNode.next = right;
	BinaryTreeNode left = treeToList(root.left);
	if (left != null) {
	    BinaryTreeNode n = left;
	    while (n.next != null) {
		n = n.next;
	    }
	    n.next = listNode;
	}
	return left != null ? left : listNode;
    }

//output: 2 5 6 10 12 13 14 15 20