CareerCup

Use a queue to do breath-first.

enque the root node into a queue
while queue is not empty
deque a node
print it's value
if the node's reference to a left child is not null
enqueu the left child node
if the node's reference to a right child is not null
enqueu the right child node

Since the given tree is not Binary tree, I assumed it an n-ary Tree. Here is my pseudo-code written in Java style for breadth first printing of a n-ary tree which will also work for a Binary tree.

/*
This is for n-ary Tree where a node can have any number of children.Such tree can be implemented with each node having only two refs - one refering to its left most child and the other refering to its iimediate sibling. This policy prevents us from having a node implemented with n references,each for a child.

We assumed node implementation class "Node" have two members - child and sibling of Node type.
Node class also has a print() method and a equals(..) method.

Queue implemented by a class "Queue" and it supports enqueue(..), dequeue() and isEmpty()methods.
isEmpty() returns true if queue is empty
*/

public void breadthFirstTraversal(Node root){

//Declare a queue
Queue children=new Queue(); //Creates an empty queue
children.enqueue(root);

while(!children.isEmpty()){
Node t=chilren.dequeue();
while(t!=null){
t.print();
if(t.child!=null){
children.enqueue(t.child);
}

//For root sibling will not be traversed
if(t.equals(root)){
t=null;
}else{
t=t.sibling;
}
}
}
}

Can Java's enqueue method add many nodes at the same time?

I think kg's algorithm just added one child to the queue. Am I missing anything?

We need a method to getChildrens of current node here so that all of them can be enqueued.

Use the same technique like that of Breadth First Search. Print the elements as you visit them.

I actually coded this and verified it works for BST's.

void BST::drawTree(node *cur) {

queue<node*> q;
q.push(root);

while (!q.empty()) {
queue<node*> r;

while (!q.empty()) {
node *cur = q.front();
cout << cur->val << " ";

if (cur->left) r.push(cur->left);
if (cur->right) r.push(cur->right);

q.pop();
}
cout << endl;
cout << "--------------------" << endl; //for delimiting level

while (!r.empty()) {
q.push(r.front());
r.pop();
}
}
}

import java.util.ArrayList;

/*
This program makes a random tree containing 1023 random
real numbers. It then computes the height of the tree and the
average depth of the leaves of the tree. Hopefully, the average
depth will tend to be close to 9, which is what it would be
if the tree were perfectly balanced. The height of the tree,
which is the same as the maximum depth of any leaf, can be
significantly larger.
*/


public class Example
{
static TreeNode root; // Pointer to the binary sort tree.
static class TreeNode
{
// An object of type TreeNode represents one node
// in a binary tree of real numbers.
double item; // The data in this node.
TreeNode left; // Pointer to left subtree.
TreeNode right; // Pointer to right subtree.
TreeNode(double x)
{
// Constructor. Make a node containing x.
item = x;
}
} // end class TreeNode

static void treeInsert(double x)
{
// Add x to the binary sort tree to which the
// global variable "root" refers.
if ( root == null )
{
// The tree is empty. Set root to point to a new node
// containing the new item.
root = new TreeNode( x );
return;
}
TreeNode runner; // Runs down the tree to find a place for newItem.
runner = root; // Start at the root.
while (true)
{
if ( x < runner.item )
{
// Since the new item is less than the item in runner,
// it belongs in the left subtree of runner. If there
// is an open space at runner.left, add a node there.
// Otherwise, advance runner down one level to the left.
if ( runner.left == null )
{
runner.left = new TreeNode( x );
return; // New item has been added to the tree.
}
else
runner = runner.left;
}
else
{
// Since the new item is greater than or equal to the
// item in runner, it belongs in the right subtree of
// runner. If there is an open space at runner.right,
// add a new node there. Otherwise, advance runner
// down one level to the right.
if ( runner.right == null )
{
runner.right = new TreeNode( x );
return; // New item has been added to the tree.
}
else
runner = runner.right;
}
} // end while
} // end treeInsert()


static int countLeaves(TreeNode node)
{
// Return the number of leaves in the tree to which node points.
if (node == null)
return 0;
else if (node.left == null && node.right == null)
return 1; // Node is a leaf.
else
return countLeaves(node.left) + countLeaves(node.right);
} // end countNodes()





static int sumOfLeafDepths( TreeNode node, int depth )
{
// When called as sumOfLeafDepths(root,0), this will compute the
// sum of the depths of all the leaves in the tree to which root
// points. When called recursively, the depth parameter gives
// the depth of the node, and the routine returns the sum of the
// depths of the leaves in the subtree to which node points.
// In each recursive call to this routine, depth goes up by one.
if ( node == null )
{
// Since the tree is empty and there are no leaves,
// the sum is zero.
return 0;
}
else if ( node.left == null && node.right == null)
{
// The node is a leaf, and there are no subtrees of node, so
// the sum of the leaf depth is just the depths of this node.
return depth;
}
else
{
// The node is not a leaf. Return the sum of the
// the depths of the leaves in the subtrees.
return sumOfLeafDepths(node.left, depth + 1)
+ sumOfLeafDepths(node.right, depth + 1);
}
} // end sumOfLeafDepth()


static int maximumLeafDepth( TreeNode node, int depth )
{
// When called as maximumLeafDepth(root,0), this will compute the
// max of the depths of all the leaves in the tree to which root
// points. When called recursively, the depth parameter gives
// the depth of the node, and the routine returns the max of the
// depths of the leaves in the subtree to which node points.
// In each recursive call to this routine, depth goes up by one.
if ( node == null )
{
// The tree is empty. Return 0.
return 0;
}
else if ( node.left == null && node.right == null)
{
// The node is a leaf, so the maximum depth in this
// subtree is the depth of this node (the only leaf
// that it contains).
return depth;
}
else
{
// Get the maximum depths for the two subtrees of this
// node. Return the larger of the two values, which
// represents the maximum in the tree overall.
int leftMax = maximumLeafDepth(node.left, depth + 1);
int rightMax = maximumLeafDepth(node.right, depth + 1);
if (leftMax > rightMax)
return leftMax;
else
return rightMax;
}
} // end sumOfLeafDepth()


public static void main(String[] args)
{
// The main routine makes the random tree and prints
// the statistics.

root = null; // Start with an empty tree. Root is a global
// variable, defined at the top of the class.

// Insert 1023 random items.

for (int i = 0; i < 1023; i++)
treeInsert(Math.random());

// Get the statistics.

int leafCount = countLeaves(root);
int depthSum = sumOfLeafDepths(root,0);
int depthMax = maximumLeafDepth(root,0);
double averageDepth = ((double)depthSum) / leafCount;

// Display the results.

System.out.println("Number of leaves: " + leafCount);
System.out.println("Average depth of leaves: " + averageDepth);
System.out.println("Maximum depth of leaves: " + depthMax);

} // end main()


}

the solution for this is a simple BFS traversal of a tree,can be found in any standard textbook.

Maintain two queues (Parent level & Current level). As you continue to traverse the tree using BFS and discover the child nodes of those in the parent level queue, push them into the Current-level queue. Once the parent-level queue is empty, swap both the queues and repeat the procedure.

Data Structures:
Queue<node> parentQ, currentQ;
Node root;
Algorithm:
1. parentQ.push(root);
2. while(parentQ is not empty) {
currNode = parentQ.pop();
for each(Node c which is a child of currNode)
currentQ.push(c);
}
3. if(currentQ is not empty) {
print(currentQ);
swap(currentQ, parentQ);
repeat 2;
}

Algo steps:

push root node in Queue
do
node = pop a node from queue
if node is null
break the loop
print node value
push node's left child in queue if non-null
push node's right child in queue if non-null
while(1)

I am posting the whole code that i was asked in riverbed interview, it took 1hr to write this.

/* This is the maximum depth that can be expected in the tree
*/
#define MAX_DEPTH 100

/* This is the maximum number of elements which we can expect in any level
*/
#define MAX_ELEMENTS 100

/* the data structure to denote the node in a binary tree*/
typedef struct node
{
struct node * left;
struct node *right;
int val;
} node;

/* This stores all the elements belonging to a specific level. The first index
* MAX_DEPTH denotes the levels, the second index MAX_ELEMENTS denotes how
* many elements can be present in each level.
*/
int elements[MAX_DEPTH][MAX_ELEMENTS];

/* This gives the max index till which the elements are filled in any level.
* So whenever a new element is added to that level, the index is incremented.
* If we look at x and y coordinates and y as levels and x as the max element
* filled in that y, this gives max x for that y.
*/
int levelindex[MAX_DEPTH];

/* This gives the max level/ depth which has been seen in the tree.
*/
int maxlevel = 0;

/* This is the function which will build the binary tree
*/
void build_tree(node **head)
{
return;
}

/* This updates the element of the current node passed at the right level,
* increments the corresponding index and calls itself recursively for its
* children. At the end of the day, "elements" is rightly populated
*/
void populate_levels(node *head, int mylevel)
{
if(head) {
/* Add this element to the correct level at the correct index
* in that level and also increment that index of that level
*/
elements[mylevel][levelindex[mylevel]++] = head->val;

/* Call recursively the same function on left and right
* children. If any of them is NULL its automatically taken
* care of
*/
populate_levels(head->left, mylevel+1);
populate_levels(head->right, mylevel+1);

/* Adjust the max level seen till now
*/
if (maxlevel < mylevel)
maxlevel = mylevel;
}
}

int main (void)
{
int i=0, j=0;

/* This is the root node of the tree that will be built
*/
node *root = NULL;

/* The below function returns the built tree starting from the root*/
build_tree(&root);

/*Initialise all elements in both arrays to zero*/
memset(elements, 0, MAX_DEPTH * MAX_ELEMENTS * sizeof(int));
memset(levelindex, 0, MAX_DEPTH * sizeof(int));

/* start off by calling it for the main root and passing the level as
* 0.
*/
populate_levels(root, 0);

/*Print the elements in the elements since they have been rightly
* populated by the recursion.
*/
for(i = 0; i <= maxlevel; i++){
for(j = 0; j < levelindex[i]; j++)
printf("%d ",elements[i][j]);
printf("\n");
}
}

package com.test;

import java.util.List;
import java.util.ArrayList;

public class TreeNode {
String value;
List<TreeNode> children=new ArrayList<TreeNode>();

public TreeNode(String x){
value = x;
}

public void addChild(TreeNode child){
children.add(child);
}

public List<TreeNode> getChildren() {
return children;
}

public String toString(){
return value;
}
}

package com.test;

import java.util.List;
import java.util.ArrayList;

public class PrintTreeLevels {
public static void printTreeLevels(TreeNode tree){
int i=1;
List<TreeNode> nodes=new ArrayList<TreeNode>();
nodes.add(tree);
while(nodes!=null && nodes.size()>0)
{
System.out.println("Level "+(i++)+": "+nodes);
nodes=getNextLevelTreeNodes(nodes);
}
}

public static List<TreeNode> getNextLevelTreeNodes(List<TreeNode> nodes){
List<TreeNode> nextLevelNodes=new ArrayList<TreeNode>();

for(TreeNode node:nodes){
nextLevelNodes.addAll(node.getChildren());
}
return nextLevelNodes;
}

public static void main(String[] args){
TreeNode a=new TreeNode("A");
TreeNode b1=new TreeNode("B1");
TreeNode b2=new TreeNode("B2");
TreeNode b3=new TreeNode("B3");
a.addChild(b1);
a.addChild(b2);
a.addChild(b3);

TreeNode c1=new TreeNode("C1");
TreeNode c2=new TreeNode("C2");
TreeNode c3=new TreeNode("C3");
TreeNode c4=new TreeNode("C4");

b1.addChild(c1);
b1.addChild(c2);
b1.addChild(c3);
b1.addChild(c4);

TreeNode c5=new TreeNode("C5");
TreeNode c6=new TreeNode("C6");
TreeNode c7=new TreeNode("C7");

b2.addChild(c5);
b2.addChild(c6);
b2.addChild(c7);

TreeNode c8=new TreeNode("C8");
TreeNode c9=new TreeNode("C9");

b3.addChild(c8);
b3.addChild(c9);

TreeNode d1=new TreeNode("D1");
TreeNode d2=new TreeNode("D2");
c5.addChild(d1);
c5.addChild(d2);

PrintTreeLevels.printTreeLevels(a);
}
}

Use BFS which do traversal level by level.

this is a simple level-order-traversal, use BFS or a Queue to mimic the same.

public void printTreeByLevel() {
		Queue<nArrayNode> queue = new LinkedList<nArrayNode>();
		if (root == null)
			return;
		queue.add(root);
		
		// Add extra null check for nodes if required
		while (queue.size() != 0) {
			nArrayNode t = queue.poll();
			for (nArrayNode temp : t.nodeList)
				queue.add(temp); 
			System.out.println(t.toString());
		}
	}

For solving the above algorithm we can go for level order traversal using a queue, like push the nodes into the queue and during popping it out print the value of the node and just check for the left and the right child of the current node if it exists then, push the nodes into the queue else, skip it. Keep repeating the process till the queue becomes empty.

Implementation:

void levelorder(struct node *root){
if(root == NULL)
return;
queue<struct node *> q;
q.push(root);
while(!q.empty()){
struct node *temp = q.front();
cout<<temp->data<<" ";
q.pop();
if(temp->left)
q.push(temp->left);
if(temp->right)
q.push(temp->right);
}

}