how would I find the level of the item in a search binary tree. Any idea. Thanks

[hav206]

template <typename T>
int BST<T>::recursive_level(BSTNode *curr, const T& item) const
{
    int level = 0;
    
    if (curr == NULL)
    {
        return -1;
    }
    
    
    
    if (curr->data < item)
    {
        level += recursive_level(curr->right, item);
    }
    if (curr->data > item)
    {
        level += recursive_level(curr->left, item);
    }
    if(curr->data == item)
    {
        return 1;
    }
    return level;
}

[kbw]

Yes, we can see what the code is doing. But it's not clear what your question is.

[hav206]

hi KBW,
What my question is How would I find the level of the item in a binary search tree?

Suppose I have to tree like this.
 
                         100
                78                  198
        76           99        187     200

If i want to know what is the level of the item 198 ?  The level should be 1. If the item is 200,, the level should be 0, how would I do i? I've been trying to solve for this almost 4 hours now. 

[kbw]

100 is at level 1, 198 at level 2 and 200 at level 3.

The code already does this (using recursion). Is the problem that you don't understand how the code works?

[jonnin]

if your tree is built off a vector underneath, it should just be a direct computation from the index "pointer" for the item.

[Kalcor]

You could use bfs to traverse the tree while keeping an array with every number's level and it's going to be the parent level + 1

So in your tree:
you'd have 100 set to level 0
and what i'll say is what bfs is going to do basically:
children of 100 are 78 and 198 so we set them both to level of 100(parent) +1 so both of them are going to be at level 1
now consider each of 78 and 198 they have 2 children each so basically, any of their children will have level 2 because each of them has the "parent+1" formula for their levels and their parents are both at level 1.

you can argue that i set 100 to level 0 well people might set it to 1 but it makes no sense to have the root set as level 1 although some people prefer to have it at 1.