title: Is it possible to build a binary tree and keep track of the median, still with O(log(n)) insertion?
body: <p>I'm trying to figure out whether this is possible. </p>
  
  <p>My attempt at an algorithm: </p>
  
  <p><code>m1,m2</code> are the middle 2 elements (If the size of the tree is odd, then <code>m1=m2</code>).</p>
  
  <p>Here's what building the tree might look like</p>
  
  <pre><code>----------------------------------
             5 = m1,m2
  ----------------------------------
             5 = m2
            /
           2 = m1
  -----------------------------------
            5 
           /
          2 = m1,m2
         /
        1
  -----------------------------------  
            5 
           /
          2 = m1
         / \ 
        1   3 = m2
  -----------------------------------
            5
           / \
          2   9 
         / \ 
        1   3 = m1,m2
  -----------------------------------
            5 = m2
           /  \
          2    9 
         / \   /
        1   \ 6   
             \
             3 = m1   
  </code></pre>
  
  <p>and I started to try and implement the method</p>
  
  <pre><code>    /// &lt;summary&gt;
      /// Insert an element
      /// &lt;/summary&gt;
      public void Insert(int val)
      {
          // If inserting first element, set _m1 and _m2.
          if(_root == null)
          {
              _m1 = _m2 = val;
          }
  
          // Insert new node in proper spot in tree.
          Node cur = _root;           
          while(cur != null)
          {
              if(cur.Val &gt; val)
                  cur = cur.Left;
              else if(cur.Val &lt; val)
                  cur = cur.Right;
              else // found value on an existing node
                  return;
          }
          cur = new Node() { Val = val };
  
          // Update median elements
          if(val &lt; _m1.Val)
          {
              // ???
          }
          else if(val &gt; _m2.Val)
          {
              // ???
          }
      }       
  }
  </code></pre>
  
  <p>but I can't figure out how to update the median. Is it even possible to do O(1) time?</p>