title: Find median in binary search tree
body: <p>Write the implementation of the function <code>T ComputeMedian() const</code> that computes the median value in the tree in O(n) time. Assume that the tree is a BST but is not necessarily balanced. Recall that the median of n numbers is defined as follows: If n is odd, the median is x such that the number of values smaller than x is equal to the number of values greater than x. If n is even, then one plus the number of values smaller 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 smaller than 7 and two values larger than 7. If we add number 3 to the set, the median becomes 5.</p>
  
  <p>Here is the class of binary search tree node:</p>
  
  <pre><code>template &lt;class T&gt;
  class BSTNode
  {
  public:
  BSTNode(T&amp; 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&lt;T&gt;;
  };
  </code></pre>
  
  <p>Binary search tree class:</p>
  
  <pre><code>template &lt;class T&gt;
  class BST
  {
  public:
  BST();
  ~BST();
  
  bool Search(T&amp; val);
  bool Search(T&amp; val, BSTNode&lt;T&gt;* node);
  void Insert(T&amp; val);
  bool DeleteNode(T&amp; val);
  
  void BFT(void);
  void PreorderDFT(void);
  void PreorderDFT(BSTNode&lt;T&gt;* node);
  void PostorderDFT(BSTNode&lt;T&gt;* node);
  void InorderDFT(BSTNode&lt;T&gt;* node);
  void ComputeNodeDepths(void);
  void ComputeNodeHeights(void);
  bool IsEmpty(void);
  void Visit(BSTNode&lt;T&gt;* node);
  void Clear(void);
  
  private:
  BSTNode&lt;T&gt; *root;
  int depth;
  int count;
  BSTNode&lt;T&gt; *med; // I've added this member data.
  
  void DelSingle(BSTNode&lt;T&gt;*&amp; ptr);
  void DelDoubleByCopying(BSTNode&lt;T&gt;* node);
  void ComputeDepth(BSTNode&lt;T&gt;* node, BSTNode&lt;T&gt;* parent);
  void ComputeHeight(BSTNode&lt;T&gt;* node);
  void Clear(BSTNode&lt;T&gt;* node);
  
  };
  </code></pre>
  
  <p>I know I should count the nodes of the tree first and then do an inorder traversal until I reach (n/2)th node and return it. I just have no clue how.</p>