CareerCup

I have an answer. Not sure if it is bug free

void treeList(struct Node * root)
{
	struct Node *lastNode = root; // End of the imaginary Queue
	struct Node *currentNode = root; // Start of the imaginary Queue
	
	while(currentNode)
	{		
		cout << currentNode->data << ' ';
		if(currentNode->left)
		{
			lastNode->next = currentNode->left;
			currentNode->left->previous = lastNode;
			lastNode = currentNode->left;
		}
		if(currentNode->right)
		{
			lastNode->next = currentNode->right;
			currentNode->right->previous = lastNode;
			lastNode = currentNode->right;
		}
		currentNode = currentNode->next;
	}
}

NULL <-------1 -------> [Node2]
                 /              \
     [Node1]<-  2 <--------------> 3 -> [Node4]
              /   \             /     \
 [Node3]<-  4<---->5<--------->6<------>7 -> [Node8]
          /  \    /   \      /   \    /   \
[Node7]<-8<-->9<->10<->11<->12<->13<->14<->15->NULL

Are we looking at something like this? if not feel free to use the above and explain.
If this is the case then we might need a pointer to go back to the parent, do we have that?

void ConvertBSTtoLL(Node *root)
  {
       queue <Node *> treeQ1;
       queue <Node *> treeQ2;
       Node *prevNode = NULL;
       if (root == NULL ) {return ; }
       treeQ1.push(root);        
       while (!treeQ1.empty()|| !treeQ2.empty())
       {
           Node *tempNode == NULL;
           while (!treeQ1.empty())
           {
               tempNode = treeQ1.pop();
               tempNode->prev = prevNode;
               if (tempNode->left  != NULL) { treeQ2.push(tempNode->left); }
               if (tempNode->right != NULL) { treeQ2.push(tempNode->right); }
               prevNode = tempNode;
           }
           if (tempNode != NULL) {
               if (treeQ2.empty()) { tempNode->next = NULL; }
               else { tempNode->next = treeQ2.front(); }
           }
           while (!treeQ2.empty())
           {
               tempNode = treeQ2.pop();
               tempNode->prev = prevNode;
               if (tempNode->left  != NULL) { treeQ1.push(tempNode->left); }
               if (tempNode->right != NULL) { treeQ1.push(tempNode->right); }        
               prevNode = tempNode;
           }
           if (tempNode != NULL) {
               if (treeQ1.empty()) { tempNode->next = NULL; }
               else { tempNode->next = treeQ1.front(); }
           }                               
       }  
  }

void TreeToList (Node* root, Node* next)
{
if (!root) return;
if (!next) next = root;
if (root->left)
{
next->next = root->left;
root->left->previous = next;
next = r->lchild;
}
if (root->right)
{
next->next = root->right;
root->right->previous = next;
next = root->right;
}
TreeToList(root->left, next);
TreeToList(root->right, next);
}

this code does not work for level 2 onwards.

This question can be done without using the next and previous pointers. This has been discussed on the forum itself if I remember. i will post the code once it is ready...

This is a duplicate of question #6070872.
Solution is posted there already which is very simple and working with no need of recursion (hence no need of stack memory space)

This is the algorithm

1) Make root->next = root->right
In recursion up to leaf nodes from root
2) if(this->right!=null) this->right->next=this->left ; apply recursion to this->right
if(this->left!=null)this->left->next=this->next->right ; apply recursion to this->left

this will give a singly linked list which can be used to make doubly linked list.

This one will work
Complexity O(n) and Space complexity O(1)

pair<node*,node*> bstTodll(node *root){
if(root==null)
return make_pair(null,null);
else{
pair<node *,node*> p1=bstTodll(root->left);
pair<node *,node*> p2=bstTodll(root->right);
if(p1.second!=null){
p1.second->next=root;
root->previous=pi.second;

}
else{
p1.second=p1.first=root;
}
if(p2.first!=null){
root->next=p2.first;
p2.first->previous=root;

}
else{
p2.first=p2.second=root;
}
return make_pair(p1.first,p2.second);

}
}

Codebuddy has already solved it. The only missing part is that root->prev should be NULL and the end of the list should be NULL. That's all.

I think first we have to do level order traversal in place means without using queue and then we can do that work simply.

code is shown below

levelorder(tree, level)
begin if tree is null, return;
if level is 1, then
if(connection != null)
{
connection->next = tree.root && tree.root -> previous = connection;
}
connection = tree.root;
}

else if(level > 1)
{
levelorder(tree.leftsubtree, level - 1);
levelorder(tree.rightsubtree, level-1);
}
}


levelorder(tree)
for d=1 to heightree
levelorder(tree,d);

Solution posted by codebuddy, on November 21, 2010 seems to be correct.