CareerCup

Can you explain a little bit more, maybe with an example?

What is the expected space complexity, because you said the solution has to be in place and then you're asking, if it can be done with one stack? I think you're confusing the problem with the spiral traversal order of a binary tree, which is done with 2 stacks, but this question is the other way around.

this can be done with the prev pointer without using the stack (even one stack)

it call fillRight and fillLeft alternatively in which there are two pointers
p iterates along the current level with the prev pointer and r iterates along the next level with the next

fill the left and right child accordingly and return the last node of the next level

for example

level 1: fill node 1 and return the last node 3
leve 2: fill node 3 and then 2 and return the last node 7
level 3: fill node 7 and return the last node 8
leve 4: fille node 8 and return null

void fillRight(ListNode node)
{
	ListNode p = node; // p iterate along the current level using the prev pointer
	ListNode prev = null;
	ListNode r = p.next; // r iterate along the next level using the next pointer
        if (r != null) 
               r.prev = null;
	while (p != null) // fill the right child first
		prev = p.prev;
		p.next = r // next for right
		if (r != null)
			r = r.next;
		p.prev = r; // prev for left
		if (r != null)
			r = r.next;		
		p = prev;		
	}		
	return r;
}
	
void fillLeft(ListNode node)
{
	ListNode p = node;
	ListNode prev = null;
	ListNode r = p.next;
        if (r != null) 
               r.prev = null;
	while (p != null) { // fill the left child first
		prev = p.prev;
		p.prev = r; // prev for left
		if (r != null)
			r = r.next;
		p.next = r; // next for right
		if (r != null)
			r = r.next;
		p = prev;
	}
	return r;
}
	
void convert(ListNode head) 
{
	ListNODE p = head;
	boolean right = true;
	while (p != null) {
		ListNode q;
		if(right) {
			q = fillRight(p);
		} else {
			q = fillLeft(p);
		}
		right = !right;
		p = q;
	}
}

We can use previous pointers of dll to do it in o(1) space.

1. We can use one stack. initialise i=0 and flag=0 stack and queue
2. if(flag==0)
insert 2^i elements and elements from stack into the queue and set flag=~flag
else
insert 2^i elements into the stack and remove element one by one and insert into the tree..set flag=~flag

3. do the above step until DLL is empty

This one uses created tree nodes to keep temporary information as tree is built, then clears leftovers. No additional stack is used.
I think that code can be made more compact.

int serialized[] = { 1, 3, 2, 4, 5, 6, 7, 10, 9, 8 };
	int length = sizeof(serialized)/sizeof(int);
		
	TreeNode *root = new TreeNode();
	root->data=serialized[0];

	TreeNode *currentParent = root;
	TreeNode *prevCreated = 0;
	bool currentParentAssigned = false;
	bool goLeft = true;

	for(int i = 1;i < length; ++i)
	{
		TreeNode *node = new TreeNode();
		node->data = serialized[i];
		
		if (goLeft)
		{
			node->right = prevCreated;
		}
		else
		{
			node->left = prevCreated;
		}

		if (currentParentAssigned)
		{
			TreeNode *nextParent=goLeft ? currentParent->left : currentParent->right;
			if (goLeft)
			{
				currentParent->left = node;
			}
			else
			{
				currentParent->right = node;
			}

			currentParent = nextParent;
			currentParentAssigned=false;
		}
		else
		{
			if (goLeft)
			{
				currentParent->right = node;
			}
			else
			{
				currentParent->left = node;
			}

			currentParentAssigned = true;
		}

		prevCreated = node;
		if (currentParent == 0)
		{
			currentParent = node;
			prevCreated = 0;
			goLeft = !goLeft;
			currentParentAssigned=false;
		}
	}

	for(int i=0;i<2;++i)
	{
		while(currentParent != 0)
		{
			TreeNode *nextParent=goLeft ? currentParent->left : currentParent->right;
			if (goLeft)
			{
				currentParent->left = 0;
			}
			else
			{
				currentParent->right = 0;
			}

			currentParent = nextParent;
		}

		currentParent = prevCreated;
		goLeft = !goLeft;
	}