Cloudera Interview Question
SDETsCountry: United States
Interview Type: Phone Interview
void print_tree(Tree tree)
{
queue q;
int lvl_size = 1;
int next_lvl_size = 0;
q.enqueue(tree);
while (!q.empty()) {
Tree t = q.pop();
if (t.left) {
next_lvl_size++;
q.enqueue(t.left);
}
if (t.right) {
next_lvl_size++;
q.enqueue(t.right);
}
print(t);
if (--lvl_size == 0) {
print(NewLine);
lvl_size = next_lvl_size;
next_lvl_size = 0;
}
}
}
static class TreeNode{
TreeNode left, right;
char c;
}
public static void printTree(TreeNode node){
if(node == null){
return;
}
Queue<TreeNode> queue = new Queue<TreeNode>(1);
Quere<TreeNode> tempQueue = new Queue<TreeNode>();
queue.add(node);
StringBuffer buffer = new StringBuffer();
while(queue.size() > 0){
buffer.setLength(0);
while(queue.peek() != null){
TreeNode workingNode = queue.poll)(;
TreeNode childNode = workingNode.left;
if(childNode != null){
tempQueue.add(childNode);
}
childNode = workingNode.right;
if(childNode != null){
tempQueue.add(childNode);
}
buffer.add(workingNode.c);
}
System.out.println(buffer.toString());
Queue tempPointer = queue;
queue = tempQueue;
tempQueue = tempPointer;
}
}
{void tree ::LevelorderTraver(Node* head)
{
queue<Node*> q;
Node* temp;
q.push(head);
int previous =1;
int index =1;
int x =0;
while(q.empty()!=1)
{
temp = q.front();
if(temp->left !=NULL){ q.push(temp->left); x++;};
if(temp->right !=NULL) {q.push(temp->right);x++;};
if(previous >=index){cout<< temp->data <<" "; index++;}
else
{
previous = x;
x=0;
index =1;
cout<<endl;
}
q.pop();
}
}
}
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
if(root == null)
return result;
queue.add(root);
while(!queue.isEmpty()) {
int levelNodes = queue.size();
List<Integer> list = new ArrayList<>();
while(levelNodes > 0) {
TreeNode n = queue.poll();
list.add(n.val);
if(n.left != null)
queue.add(n.left);
if(n.right != null)
queue.add(n.right);
levelNodes--;
}
result.add(list);
}
return result;
}
/* ZoomBA.
Level order traversal.
The key is to understand that,
you need to maintain two queues, one for current,
another for next level.
After a level is exhausted,
one needs to replace that queue by the one from built up
*/
def level_order( root ){
cur = list( root ) // current level
while ( !empty(cur) ){
// get one and go along with it
node = cur.dequeue()
printf(' %s ', node.value ) // print it
next = list()
for ( child : node.children ){
next.enqueue( child ) // queue it
}
println() // completes the level
cur = next // switch the level
}
}
Run DFS with Queue and print layer by layer..
- naren December 12, 2014