CareerCup

For a spiral level print, odd levels should be printed from left to right and even from right to left. This is a small variation in BFS style traversal. We can use many data structures but for me the one that I would use is a Deque(Double Ended Queue). Efficient and can work like both a stack and a queue.

it can be done just using the two stacks like in when we do the spiral order traversal and maintaing the prev pointer every time
code for this

struct node *BTtoDLLSPiral(struct node *L)
{
struct node *temp,*temp1,*head=NULL;
struct node *prev=NULL;
Stack s1,s2;
Push(s1,L);
while(!isEmpty(s1)||!isEmpty(s2))
{
while(!isEmpty(s1))
{

if(!head)
{
head=pop();
temp1=head;
if(temp1->left)
Push(s2,temp1->left);
if(temp1->right)
Push(s2,temp1->right);
head->left=prev;
prev=head;
}
else
{
temp1=pop();
prev->right=temp1;
if(temp1->left)
Push(s2,temp1->left);
if(temp1->right)
Push(s2,temp1->right);
temp1->left=prev;
prev=temp1;
}
while(!isEmpty(s2))
{
temp1=pop();
prev->right=temp1;
if(temp1->right)
Push(s1,temp1->right);
if(temp1->left)
Push(s1,temp1->left);
temp1->left=prev;
prev=temp1;
}
}

return head;

}



}

Java code is as follows
/**
* This method returns the Circular Doubly Linked List
* representation of the inordered sequence of BST Nodes
* The node of DLL here is not a DLLNode, but its BTNode
* where getLeft() means getPrevious() and getRight() means
* getNext()
* @param rootNode
* @return
*/
public static BTNode convertBSTToDLL(BTNode rootNode){

if (rootNode==null) return(null);
BTNode leftNode = convertBSTToDLL(rootNode.getLeft());
BTNode rightNode = convertBSTToDLL(rootNode.getRight());

rootNode.setLeft(rootNode);
rootNode.setRight(rootNode);

BTNode dllHeadNode = append(leftNode,rootNode);
dllHeadNode = append(dllHeadNode,rightNode);

return dllHeadNode;
}

private static BTNode append(BTNode a, BTNode b) {
// if either is null, return the other
if (a==null) return(b);
if (b==null) return(a);

BTNode aLast = a;
while(aLast != null){
aLast = aLast.getRight();
if(aLast.getRight() == a) break;
}

BTNode bLast = b;
while(bLast != null){
bLast = bLast.getRight();
if(bLast.getRight() == b) break;
}

aLast.setRight(b);
b.setLeft(aLast);

bLast.setRight(a);
a.setLeft(bLast);

return a;
}

it evaluates level of node while moving in BFS order. For even levels it enters the item in a Stack and empties it when size of stack =2^level. For odd levels it simply prints in normal level order.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class LevelOrderPrint <T extends Comparable<T>> {
//BFS method
public static void BFS(BTreeNode root){
Queue<BTreeNode> queue = new LinkedList<BTreeNode>();
Stack<Integer > st =new Stack<Integer>();
if(root!=null)
queue.add((BTreeNode) root);
while(!queue.isEmpty()){
root=queue.remove();
if(root.mark==false)
{
root.mark=true;
if(root.level%2==0){
st.push(root.val);
if(st!=null&&st.size()==Math.pow(2,root.level)){

while(st.size()>0)
System.out.print(st.pop()+" ");
}
}
else
{System.out.print(root.val+" ");

}
}
if(root.left!=null)
{root.left.level=root.level+1;
queue.add(root.left);
}
if(root.right!=null)
{root.right.level=root.level+1;
queue.add(root.right);
}

}

I doubt if we can do it inplace using only left and right pointers

Ｍy solution: ( level-travel with queue, a stack and a level count is used for spiral sequence ) this is a inplace algo, left pointer serve as previous and right pointer serve as next pointer
in doubly linked list ....

void TreeToDoubleLinkedList ( Node *root )
{
queue<Node *> que;
stack<Node *> stk;
Node *prev = NULL;
Node *current;
int level = 1;

que.push( root );
que.push( NULL ); /* NULL serve as level delimitor */

while ( !que.empty() )
{
current = que.pop();
if ( current == NULL ) /* this level finished */
{
while ( !stk.empty() )
que.push ( stk.pop() ) ;
que.push( NULL );
level++;
current = que.pop();
}

/* process current node */
if ( previous )
previous->right = current ;
current->left = previous;
previous = current ;

/* level 1,3,5,7.... */
if ( level%2 == 1 )
{
stk.push( current->right );
stk.push( current->left );
}
/* level 2,4,6..... */
else
{
stk.push( current->left );
stk.push( current->right );
}
}

current->right = NULL;
}

For odd levels, do print(this), print(left), print(right).
For even levels do print(this), print(right), print(left).

So it is just BFS but switching orders of right and left according to level.

TL(n, b)
	if(n == NULL)
		return NULL
	n->l = TL(n->l, 0)
	n->r = TL(n->r, 1)
	ret = n
	if(n->r)
		n->r->l = n
		if(b)
			ret = n->r
	if(n->l)
		n->l->r = n
		if(!b)
			ret = n->l
	return ret