Escreva a implementação da funçãoT ComputeMedian() const que calcula o valor mediano na árvore em O (n) tempo. Suponha que a árvore seja um BST, mas não seja necessariamente equilibrada. Lembre-se de que a mediana de n números é definida da seguinte maneira: Se n for ímpar, a mediana será x, de modo que o número de valores menores que x seja igual ao número de valores maiores que x. Se n for par, então um mais o número de valores menores que x é igual ao número de valores maiores que x. Por exemplo, dados os números 8, 7, 2, 5, 9, a mediana é 7, porque existem dois valores menores que 7 e dois maiores que 7. Se adicionarmos o número 3 ao conjunto, a mediana se tornará 5.

Aqui está a classe do nó da árvore de pesquisa binária:

template <class T>
class BSTNode
{
public:
BSTNode(T& val, BSTNode* left, BSTNode* right);
~BSTNode();
T GetVal();
BSTNode* GetLeft();
BSTNode* GetRight();

private:
T val;
BSTNode* left;
BSTNode* right;  
BSTNode* parent; //ONLY INSERT IS READY TO UPDATE THIS MEMBER DATA
int depth, height;
friend class BST<T>;
};

Classe da árvore de pesquisa binária:

template <class T>
class BST
{
public:
BST();
~BST();

bool Search(T& val);
bool Search(T& val, BSTNode<T>* node);
void Insert(T& val);
bool DeleteNode(T& val);

void BFT(void);
void PreorderDFT(void);
void PreorderDFT(BSTNode<T>* node);
void PostorderDFT(BSTNode<T>* node);
void InorderDFT(BSTNode<T>* node);
void ComputeNodeDepths(void);
void ComputeNodeHeights(void);
bool IsEmpty(void);
void Visit(BSTNode<T>* node);
void Clear(void);

private:
BSTNode<T> *root;
int depth;
int count;
BSTNode<T> *med; // I've added this member data.

void DelSingle(BSTNode<T>*& ptr);
void DelDoubleByCopying(BSTNode<T>* node);
void ComputeDepth(BSTNode<T>* node, BSTNode<T>* parent);
void ComputeHeight(BSTNode<T>* node);
void Clear(BSTNode<T>* node);

};

Eu sei que devo contar os nós da árvore primeiro e, em seguida, fazer uma travessia inorder até alcançar (n / 2) o nó e devolvê-lo. Eu simplesmente não tenho idéia de como.