SAS Research Interview Question
Software Engineer / DevelopersTeam: BIRD
Country: India
Interview Type: In-Person
Problem: Implement level search (search level by level for a particular element) in a binary search tree)
EX: 1
/ \
2 3
/ \ / \
4 5 6 7
In the above tree level-0 --> 1
level-1 --> 2, 3
level-2 --> 4, 5, 6, 7
Solution:
// We need a Queue inorder to perform a search level by level. This queue will maintain the elements for each level.
int find_num(Tree *T, Queue *Q, int n)
{
if (Q.Empty() == true)
return -1;
int num = Q.Deque();
if (num == n)
{
cout << "found the number " << n ;
return 0;
}
if (T->left != null)
{
Q.Enqueue(T->left->data);
}
if (T->right != null)
{
Q.Enqueue(T->left->data);
}
if (T->left != null)
{
find_num(T->left, Q, n);
}
if ( T->right != null)
{
find_num(T->right, Q, n);
}
}
what is that? please explain your question in more details if possible
- loveCoding December 23, 2011