Find median in binary search tree

Question

Write an implementation of the T ComputeMedian() const function, which calculates the median value in the tree in O (n) time. Suppose the tree is BST, but not necessarily balanced. Recall that the median of n numbers is defined as follows: if n is odd, the median is x, so that the number of values ​​less than x is equal to the number of values ​​greater than x. If n is even, then one plus the number of values ​​less than x is equal to the number of values ​​greater than x. For example, given the numbers 8, 7, 2, 5, 9, the median is 7, because there are two values ​​less than 7 and two values ​​greater than 7. If we add the number 3 to the set, the median will become 5.

Here is the node binary search tree class:

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

Search tree binary class:

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

I know that I must first count the nodes of the tree, and then do a roundabout until I get to the (n / 2) th node and return it. I just have no idea.

Answer 1

As you already mentioned, it is fairly easy to first find the number of nodes by doing any crawl:

 findNumNodes(node): if node == null: return 0 return findNumNodes(node.left) + findNumNodes(node.right) + 1 

Then with a workaround that breaks when the number of node is n / 2:

 index=0 //id is a global variable / class variable, or any other variable that is constant between all calls findMedian(node): if node == null: return null cand = findMedian(node.left) if cand != null: return cand if index == n/2: return node index = index + 1 return findMedian(node.right) 

The idea is that the queues of the bypass nodes in the BST are sorted. So, since the tree is a BST, the process i th node that you are processing is i th node in order, this of course is also true for i==n/2 , and when you find that it is n/2 th node , you will return it.

---

As an additional note, you can add functionality to BST to efficiently find the i element ( O(h) , where h is the height of the tree) using sort statistics trees .