CareerCup

Do level order traversal of the tree and check for the searching element:
int binarytree_search(node *root,int x)
{
int level=0;
node *temp;
queue<node*>q;
q.enqueue(root);
while(!q.empty())
{
temp=q.dequeue();
if(temp->data==x)
return level;
if(temp->left)
q.enqueue(temp->left);
if(temp->right)
q.enqueue(temp->right);
}
//if control reaches till here return -1
return -1;
}
TC: O(n)
SC:O(n)

as such there is no preference to using BFT/DFT etc...anyone of them will do the job as long as you are checking for the given value...that apart the code seems to assume that there is some other function for getting the level of a node, is it? then that function will just take a node data and return its level, right?

int findLevel(TREE * t,int levelCount,int data)
{

int left,right;
if(!t)
return -1;
if(t->data == data )
{
return 1;

}
else
{
left=findLevel(t->left,data);
right= findLevel(t->right,data);

return (left== -1) ? right: left;

}





}

Perfectly Working Code!!!!

int findLevel(TREE * t,int& levelCount,int data)
{

int left,right,temp;
if(!t)
return -1;
if(t->data == data )
{
levelCount=0;
return 1;

}
else
{

left=findLevel(t->left,levelCount,data);
right= findLevel(t->right,levelCount,data);
temp=(left == -1 ) ? right: left;
levelCount++;
return temp ;

}





}

BFS.

int getDepthOfItem(node* root, int x) {
queue<node*> q;
int i = 0;

q.push(root);

do {
if (q.front()->value == x) return (int) log2(i + 1);
if (q.front()->left) q.push(q.front()->left);
if (q.front()->right) q.push(q.front()->right);
q.pop();
++i;
} while (!q.empty());

return -1;
}

Reposting, whitespace preserved this time:

BFS.

int getDepthOfItem(node* root, int x) {
queue<node*> q;
int i = 0;

q.push(root);

do {
if (q.front()->value == x) return (int) log2(i + 1);
if (q.front()->left) q.push(q.front()->left);
if (q.front()->right) q.push(q.front()->right);
q.pop();
++i;
} while (!q.empty());

return -1;
}

int searchbtree(node *root, int value){

int left, right;

if(root == NULL) return -1;

if(root->data == value) return 0;

left = searchbtree(root->left, value);

right = searchbtree(root->right, value);

if(left >= 0) return (1 + left);

if(right >= 0) return (1 + right);

return -1;

}

struct node
{
int data;

struct node*left;
struct node*right;
};

int getDepthOfItem(node* root, int x)
{
node t,w;

queue<node*> Q;

Q.push(root);
int level=0;

while(!Q.empty())
{
t=*Q.front();
Q.pop();

if(t.data==x)
return level;

Q.push(&t.right);
Q.push(&t.left);

level++;

}

return -1;

}

the code is wrong @ Anonymous
else prove why its not wrong?

A simple DFS is sufficient for this

int findlevel(tree* root, int key , int level = 0)
{
if(!root) return -1;
if(root->data == key) return level;
if( findlevel(root->left,key,level+1) > 0 || findlevel(root->right,key,level+1))return level;
return -1;
}

I have not ran the code on system though.

as we do not have any standard way to searching for elements in a binary tree, unlike a BST, we've to follow the standard method of searching the element by traversing the whole tree and one of the option would be to use level-order-traversal[BFS]

typedef struct tree
{
tree *right;
tree *left;
int data;
}node;

int findLevel(node *start)
{

}

Apply BFS and store a null pointer in a queue at the start. Now Whenever you find out a NULL pointer in queue push a NULL pointer again and increase the count. The final count will be our level.

typedef struct tree
{
tree *right;
tree *left;
int data;
}node;

int findLevel(node *start, int key)
{
   queue<node*> level;
   level.push(start);
   level.push(NULL);
   int count = 0; 
   while(level.size()>0)
   {
      start = level.front();
      level.pop();
      if(start == NULL)
      {
         count++;
         if(level.front()!= NULL)
             level.push(NULL);
         continue;
      } 
      if (start->data == key) return count;
      if(start->left)level.push(start->left);
      if(start->right)level.push(start->right);  
   }
   return -1;   
}

Tree Traversl algo

leveller(node *x, int toSearch, int level)
{
if (x==NULL)
return;
if (x->key==toSearch)
    cout<<"Match at level "<<level;
leveller(x->left,toSearch,level+1);
leveller(x->right,toSearch,level+1)
}

call---> search_depth(my_t, val, 0);

int search_depth(struct bin_t * my_t, int val, int dp)
{
if (!my_tr) {
return -1;
}
if (my_tr->val == val) {
printf("\n val : %d depth %d\n", my_tr->val, dp);
} else if (my_tr->val > val) {
pr_t(my_tr->l_ch, val, ++dp);
} else {
pr_t(my_tr->r_ch, val, ++dp);
}
return 0;
}

code tested ...
int level_find(Node *cur, int value, int level)
{
   if(!cur)
        return -1;

   if(cur->data == value)
        return level;

   int left = level_find(cur->left, value, level+1);
   int right = level_find(cur->right, value, level+1);

   if(left!=-1)
       return left;
   else if(right!=-1)
       return right;
   else
       return -1;
}

int level_find_wrap(Node *cur, int value)
{
   return(level_find(cur, value, 0));
}

int level_node(Tree *node, int level, int data)
{
if(node != NULL)
{
if(node->data == data)
return level;
else if(data < node->data)
level_node(node->left,level+1,data);
else
level_node(node->right,level+1,data);
}
else
return -1;
}

int levelSearch (Node *node, int data, int level = 1)
{
    if (!node)
        return -1;
    if (node->info == data)
        return level;
    return (MAX (levelSearch (node->left, data, level + 1), levelSearch (node->right data, level + 1))
}

What about using preorder traversal??? It should work...If not found, it returns -1 else it returns the level of the node containing key.

int search(Tree *node, int key)
{
if(node)
{
if(node->data == key) return 0;
return (1 + search(root->left, key);
return (1 + search(root->right, key);
return -1;
}

return -1;
}