Напишите реализацию функцииT ComputeMedian() const который вычисляет медианное значение в дереве за O (n) времени. Предположим, что дерево является BST, но не обязательно сбалансировано. Напомним, что медиана из n чисел определяется следующим образом: если n нечетно, медиана равна x так, что число значений, меньших, чем x, равно количеству значений, превышающих x. Если n четное, то один плюс количество значений, меньших, чем x, равно количеству значений, превышающих x. Например, учитывая числа 8, 7, 2, 5, 9, медиана равна 7, потому что есть два значения меньше 7 и два значения больше 7. Если мы добавим число 3 к набору, медиана станет 5.

Вот класс узла бинарного дерева поиска:

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

Класс бинарного дерева поиска:

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

};

Я знаю, что должен сначала посчитать узлы дерева, а затем выполнить обход по порядку, пока не достигну (n / 2) -го узла и верну его. Я просто понятия не имею, как.