CareerCup

Can you please explain the question in detail
I am not able to understand what this label is

- DashDash April 12, 2012 | Flag Reply

As far as I understand the question, it is a BFS for a Binary Search Tree

- Anonymous April 12, 2012 | Flag Reply

As far as I understand the question, it is a BFS for a Binary Search Tree

- Anonymous April 12, 2012 | Flag Reply

it is a BFS traversal .. just insert a new line and the label after each level ... check out the previous posts .. can be done in O(n)

- viks April 13, 2012 | Flag Reply

I think the problem is a little modification of BFS, what is expected here is that you print all the nodes levelwise...e.g. assume a complete BST with nodes "2 7 9 11 13 16 19", where the order given earlier is the result of inorder traversal..then the output should be

11
7 16
2 9 13 19

where 11 is the root, on next lines its children, 7 and 16, on next line their children etc .. the code given below does that, it

public static void newLevelWise(Node head){

        Vector<Node> q = new Vector<Node>();
        Node ref1=null;
        Node ref2=null;
        q.add(null);
        q.add(head);

        while(q.size()>0){
                ref1 = q.remove(0);
                if(ref1==null){
                        if(q.size()==0){
                                return;
                        }

                        ref2=q.remove(0);
                        System.out.println("");
                        System.out.print(ref2+" ");
                        q.add(null);
                        if(ref2.left!=null){
                                q.add(ref2.left);
                        }

                        if(ref2.right!=null){
                                q.add(ref2.right);

                        }
                        
                }else{

                        System.out.print(ref1+" ");
                        if(ref1.left!=null){
                                q.add(ref1.left);
                        }

                        if(ref1.right!=null){
                                q.add(ref1.right);

                        }


                }
        }

}

- Tintin April 13, 2012 | Flag Reply

// BFSTree.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

struct Tree
{
int data;
Tree *left;
Tree *right;
};

struct linkedList
{
Tree *node;
linkedList *next;
};

Tree * CreateTree(Tree *root, int value)
{
if(root == NULL)
{
root = new Tree();
root->data = value;
root->left = NULL;
root->right = NULL;
}
else if(value < root->data)
root->left = CreateTree(root->left, value);
else
root->right = CreateTree(root->right, value);

return root;
}

void PrintTreeBFS(linkedList *current, linkedList *last)
{
if(current == NULL)
return;
else
{
//printf("\n Node Value %d" + current->node->data);
printf("\n Node Value %d", current->node->data);
if(current->node->left != NULL)
{
linkedList *onemore = new linkedList();
onemore->node = current->node->left;
onemore->next = NULL;
last->next = onemore;
last = last->next;

}

if(current->node->right != NULL)
{
linkedList *another = new linkedList();
another->node = current->node->right;
another->next = NULL;
last->next = another;
last = last->next;
}

current = current->next;
PrintTreeBFS(current, last);
}

}

int _tmain(int argc, _TCHAR* argv[])
{

int arr[] = {30,15,10,66,51,53,12};
linkedList *list = new linkedList();
Tree *root = NULL;

for(int i=0; i< 7; i++)
root = CreateTree(root, arr[i]);
list->node = root;
list->next = NULL;

PrintTreeBFS(list, list);

return 0;
}

- DashDash April 18, 2012 | Flag Reply

void PrintTreeBFS (Node *n) {{{ if (n == null) return; queue<Node> myQ; queue<int> myLevel; int currentLevel = 0; cout << n->data; if (n->left != null) {{{ myQ.push(n->left); currentLevel ++; myLevel.push(currentLevel); }}} if (n->right != null) {{{ myQ.push(n->right); myLevel.push(currentLevel); }}} while (myQ.size > 0) {{{ Node tmp = myQ.pop(); int lastLevel = myLevel.pop(); if (currentLevel == lastLevel) cout<<"\n"; cout<< tmp->data; if (tmp->left != null) {{{ myQ.push(tmp->left); myLevel.push(lastLevel+1); currentLevel = lastLevel +1; }}} if (tmp->right != null) {{{ myQ.push(tmp->right); myLevel.push(lastLevel+1); }}} }}} }}} - Jo April 24, 2012 | Flag Reply