CareerCup

If a node has right child, append it to the leftmost child ( keep on follow the left child of the nodes, until you reach a node whose left child is null). conver the link between the node and its child to a doubly linked list. Now start the algorithm again from the left child. Repeat the algorithm until no node has right child.

can't we use a queue for this purpose ??

// tree element
struct TreeEl
{
TreeEl* left;
TreeEl* right;
int data;
};


void TreeToList(TreeEl* curEl) // give root of tree
{
if (curEl->left)
TreeToList(curEl->left);

static TreeEl* prevEl = NULL;

if (prevEl)
{
prevEl->right = curEl;
curEl->left = prevEl;
}

prevEl = curEl;

if (curEl->right)
TreeToList(curEl->right);
}

static void Main(string[] args)
{
BinarySearchTree<int> bst = new BinarySearchTree<int>();
int[] arr = { 15, 6, 18, 3, 7, 17, 20, 2, 4, 13,9 };
for (int i = 0; i < arr.Length; i++)
{
bst.Insert(arr[i]);
}
TreeNode<int> head = null;
TreeNode<int> last = null;
FlatBst(bst.Root,ref last,ref head);
TreeNode<int> node = head;
while (node != null)
{
Console.Write(node.Element);
Console.Write(" ");
node = node.Right;
}
Console.Read();
}

static void FlatBst(TreeNode<int> node,ref TreeNode<int> prev,ref TreeNode<int> head)
{
if (node != null)
{
FlatBst(node.Left,ref prev,ref head);
node.Left = prev;
if (prev== null)
{
head = node;
}
else
prev.Right = node;
prev = node;
FlatBst(node.Right,ref prev,ref head);
}
}

struct node *linearizeR(struct node *currHead){

	if(currHead->right == NULL && currHead->left == NULL)
		return currHead;

	if(currHead->right == NULL){
		currHead->left = linearizeL(currHead->left);
		currHead->left->right = currHead;
		currHead->left->left = findParent(currHead);
		return currHead->left;
	}
	if(currHead->left == NULL){
		currHead->right = linearizeR(currHead->right);
		return currHead;
	}	

	//linearize right tree and return left
	currHead->right = linearizeR(currHead->right);
	currHead->left = linearizeL(currHead->left);
	currHead->left->right = currHead;
	currHead->left->left = findParent(currHead);
	return currHead->left;	

}

struct node *linearizeL(struct node *currHead){

	if(currHead->right == NULL && currHead->left == NULL)
		return currHead;

	if(currHead->right == NULL){
		currHead->left = linearizeL(currHead->left);
		return currHead;
	}
	if(currHead->left == NULL){
		currHead->right = linearizeR(currHead->right);
		currHead->right->left = currHead;
		currHead->right->right = findParent(currHead);
		return currHead->right;
	}	

	//linearize right tree and return left

	currHead->right = linearizeR(currHead->right);
	currHead->left = linearizeL(currHead->left);
	//make sure the right ka left points to currHead and right ka right points to currHead->parent!
	currHead->right->left = currHead;
	currHead->right->right = findParent(currHead);
	return currHead->right;	
	
}

the above two functions linearize the tree to doubly linked list..recursively...

not using extra memory means no extra memory for any new node, it doesnot means u cant use Queue for this.

static TreeJ prev1=null;
	void binaryTree2DoubleLinkedList(TreeJ root, TreeJ doublyLL)
	{
	    // Base case
	    if (root == null){
	    	return;
	    }
	 
	    // Recursively convert left subtree
	    binaryTree2DoubleLinkedList(root.left, doublyLL);
	 
	    // Now convert this node
	    if (prev1 == null){
	    	doublyLL = root;
	    }
	    else {
	        root.left = prev1;
	        prev1.right = root;
	    }
	    prev1=root;
	 
	    // Finally convert right subtree
	    binaryTree2DoubleLinkedList(root.right, doublyLL);
	}

// This is a modified in-order traversal adapted to this problem.
// prev (init to NULL) is used to keep track of previously traversed node.
// head pointer is updated with the list's head as recursion ends.
void treeToDoublyList(Node *p, Node *& prev, Node *& head) {
if (!p) return;
treeToDoublyList(p->left, prev, head);
// current node's left points to previous node
p->left = prev;
if (prev)
prev->right = p; // previous node's right points to current node
else
head = p; // current node (smallest element) is head of
// the list if previous node is not available
// as soon as the recursion ends, the head's left pointer
// points to the last node, and the last node's right pointer
// points to the head pointer.
Node *right = p->right;
head->left = p;
p->right = head;
// updates previous node
prev = p;
treeToDoublyList(right, prev, head);
}

// Given an ordered binary tree, returns a sorted circular
// doubly-linked list. The conversion is done in-place.
Node* treeToDoublyList(Node *root) {
Node *prev = NULL;
Node *head = NULL;
treeToDoublyList(root, prev, head);
return head;
}

There is a way to do the job in place.
Start from root,
1- go to the right node, lets say setPoint node,
2- if there is any node in left, move this node to the most right node of setPoint
3- if there is NULL in setPoint->left, point to the setPoint's parent (we are going to make a double link list)
4- continue from step 1 with Setpoint->right until the end of chain

now with the same logic apply the algorithm with root->left

at the end we have a double linked list

here is the code in C

of course the complexity of this method is o(n^2) while for each node is needed to trace all left or right nodes.

Any suggestion? better idea?

/* Flatten BST*/
node * flattenBST(node* head)
{
	node *h=head;
	while(h->right!=NULL)
	{
		if(h->right->left!=NULL)
		{
			node *mostRight, *setPoint;
			setPoint=mostRight=h->right;
			while(mostRight->right!=NULL)
				mostRight=mostRight->right;
			mostRight->right=setPoint->left;
			setPoint->left=h;
		}
		else
			h->right->left=h;
		h=h->right;
	}
	h=head;
	while(h->left!=NULL)
	{
		if(h->left->right!=NULL)
		{
			node *mostLeft, *setPoint;
			setPoint=mostLeft=h->left;
			while(mostLeft->left!=NULL)
				mostLeft=mostLeft->left;
			mostLeft->left=setPoint->right;
			setPoint->right=h;
		}
		else
			h->left->right=h;
		h=h->left;
	}
	return h;
}

int bst2dll(struct node* root, struct node** head ){
    queue<struct node* > Q;
    Q.push(root);
    
    *head = root;
    struct node* last= NULL;
    struct node* node= NULL;
    
    while ( !Q.empty()){
        node = Q.front();
        Q.pop();
        if(node->left)
            Q.push(node->left);
        
        if(node->right)
            Q.push(node->right);
        
        node->left = last;
        node->right = Q.front();
        last = node;  
    }
   
 
}

To understand this concept you may watch this video tutorial
youtube.com/watch?v=WJZtqZJpSlQ

Testing indentation of the code

for(int i=0;i <10; i++)
{
     System.out.print();
}