Escribe la implementación de la funciónT ComputeMedian() const que calcula el valor medio en el árbol en O (n) tiempo. Suponga que el árbol es un BST pero no está necesariamente equilibrado. Recuerde que la mediana de n números se define de la siguiente manera: si n es impar, la mediana es x tal que el número de valores menores que x es igual al número de valores mayores que x. Si n es par, entonces uno más el número de valores menores que x es igual al número de valores mayores que x. Por ejemplo, dados los números 8, 7, 2, 5, 9, la mediana es 7, porque hay dos valores menores que 7 y dos valores mayores que 7. Si sumamos el número 3 al conjunto, la mediana se convierte en 5.

Aquí está la clase del nodo del árbol de búsqueda binaria:

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>;
};

Clase de árbol de búsqueda binaria:

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);

};

Sé que primero debo contar los nodos del árbol y luego hacer un recorrido en orden hasta llegar al (n / 2) th nodo y devolverlo. Simplemente no tengo idea de cómo.