CareerCup

public static void traverse(Node node) {
	if (node == null) return;
	List<Node> thisLevel = new ArrayList<Node>();
	thisLevel.add(node);
	while (!thisLevel.isEmpty()) {
		List<Node> nextLevel = new ArrayList<Node>();
		for (Node n : thisLevel) {
			System.out.print(n.key() + " ");
			if (n.left() != null) nextLevel.add(n.left());
			if (n.right() != null) nextLevel.add(n.right());
		}
		thisLevel = nextLevel;
		System.out.println();
	}
}

BFS traversal using Two Queues for line breaks.

it can be done by the use of only one queue also...if the end of each level is marked by the null in the queue....

void Level(root)
{
int h=height(root);

for(i=1;i<=h;i++)
{
LEVELORDER(root,i);
printf("\n");
}
}


void LEVELORDER(root,level)
{
if(!root)
return NULL;

if(level==1)
printf("%d ",root->data);

else if(level>1)
{
LEVELORDER(root->left,level-1)
LEVELORDER(root->right,level-1)
}

}

void printtree(Node* p,int level) {

vector<Node*> av;
av.push_back(p);
map<int,vector<Node*> > amap;

amap[0]=av;
while(true) {
vector<Node*> nodev;
for(int i=0;i<amap[level].size();i++) {
Node* an = amap[level][i];
cout << an->num << endl;
if (an->left!=NULL) {
nodev.push_back(an->left);
}
if (an->right!=NULL) {
nodev.push_back(an->right);
}

}

if (nodev.size()>0) {
amap[++level]=nodev;
}
else
break;
}
}
void print(Node* p) {
printtree(p,0);
}

Cant you just get the pre-order of the tree. Iterate through a look (0...n; n being height of the tree) and keep printing 2^n objects from the pre-order list each time?

Start traversing the tree after putting Root and new line in list. and then append new line whenever see new line in the list.
pseudo code:::

Tree *node=root;
list.push_back(node);
list.push_back(new_line_node);
while(node != null)
{
if (node->left != null)
list.push_back(node->left)
if (node->right != null)
list.push_back(node->right)

print (node->value)

if (list.pop_front == new_line_node)
{
print "\n"
list.push_back(new_line_node)
}
else
node=list.pop_front();
}

Couldn't we maintain a single queue and push every element in along with it's level number (which is level number of parent + 1). We also maintain a variable for the current level. Whenever the element popped out has a level number greater than the current level, we go to a new line and increment the current level number before continuing as before.

Couldn't we maintain a single queue and push the left and right children of each node popped out along as a new object with an associated level number (which is level number of parent + 1). We also maintain a variable for the current level. Whenever the element popped out has a level number greater than the current level, we go to a new line and increment the current level number before continuing as before.

typedef struct TreeNode 
{
  int element;
  struct TreeNode *left, *right;
} TreeNode;

TreeNode *displayTree(TreeNode *node)
{
  //display the full tree
  if(node==NULL)
  {
    return;
  }
  displayTree(node->left);
  printf("| %d ", node->element); 
  displayTree(node->right);
}