CODEWITHSUNDEEP
c++data-structuresbinary-search-tree
Vladar Akos
Vladar Akos

Reputation: 5

Can I find the position of a given value in a Binary Search Tree better?

I need some help on how to find the (sorted) position of a given value in a Binary Search Tree better than I already did (if possible).

I have another method that searches for the i-th element of the tree and returns the node. So basically I solved the problem by searching through the tree until I find the given value or the node's data is bigger than the value I am searching for.

Our teacher gave us the algorithm on how to find the i-th element by knowing how many elements are there in that subtree. That is why I am wondering if my problem can be done in less steps?

Thanks in advance!

This is the not so optimal solution: 

template <class T>
int BST<T>::Rang(const T& x) {

int meret = root->size;     //meret = size of the whole 
                            //tree
Node<T>* temp = i_th_Node_rec(1, root);
int i = 1;
while (temp && i <= meret && x != temp->data && x < temp->data) {
    ++i;
    temp = i_th_Node_rec(i, root);
}

return (i < meret) ? i : -1;
}

Upvotes: 0

Views: 1377

Answers (1)

molbdnilo
molbdnilo

Reputation: 66451

It's very similar to how you locate the i:th node, but "in reverse".

  • If the element is in the root, its position is the size of the left subtree.
  • If the element is to the left, its position is the same as its position in that subtree.
  • If the element is to the right, its position is its position in that subtree, plus the size of the root's left subtree, plus one.

Upvotes: 3

Related Questions