title: Find and Delete Median In C Binary Search Tree
body: <p>I am working on Data structures in C and i need to find the Median of the values in the B.S.T and delete the median then showcase the new B.S.T but i haven't managed.I don't really know where am going wrong.Please help me out on this. I also need to be able to find a value that is closest to the mean and delete it</p>
  
  <pre><code>#include&lt;stdio.h&gt;
  #include&lt;stdlib.h&gt;
  
  struct Node
  {
  int key;
  struct Node* left, *right;
  };
  
  //Function to create new BST NODE
  struct Node *newNode (int item)
  {
  struct Node *temp = (struct Node *)malloc(sizeof(struct Node));
  temp-&gt;key = item;
  temp-&gt;left = temp-&gt;right = NULL;
  return temp;
  }
  //Function to perform INORDER traversal operation
  void inorder(struct Node *root)
  {
  if(root!=NULL)
  {
  inorder(root-&gt;left);
  printf("%d\n",root-&gt;key);
  inorder (root-&gt;right);
  }
  } 
  //Function to insert new node with given key in BST
  struct Node* insert (struct Node* node, int key)
  {
  //if tree is empty
  if(node==NULL) return newNode(key);
  //else, recur down the tree
  if(key&lt; node-&gt;key)
  node-&gt;left  = insert(node-&gt;left,key);
  else if(key &gt; node-&gt;key)
  node-&gt;right  = insert(node-&gt;right,key);
  //Return the (unchanged) node pointer
  return node;    
  }
  
  
  //Given a non-empty BST ,return node with minimum key value found in that          tree. Whole tree not really searched
  struct Node * minValueNode(struct Node* node)
  {
  struct Node* current =node;
  //loop down to find the left-most leaf
  while (current-&gt;left !=NULL)
      current = current-&gt;left;
  return current;
  }
  //Given the BST and key, function to deleted the key to return new root
  struct Node* deleteNode(struct Node* root, int key)
  {
  if(root == NULL) return root;
  if(key&lt;root-&gt;key)
      root-&gt;left = deleteNode(root-&gt;left,key);
  else if (key&gt; root-&gt;key)
      root-&gt;right = deleteNode(root-&gt;right, key);
  else
  {
      //node with one or no child
      if(root-&gt;left == NULL)
      {
          struct Node *temp = root-&gt;right;
          free(root);
          return temp;
      }
   else if (root-&gt;right == NULL)
   {
      struct Node *temp = root-&gt;left;
      free(root);
      return temp;
  }
  //node with two children
  struct Node* temp = minValueNode(root-&gt;right);
  //copy the inorder successor to this node
  root-&gt;key = temp-&gt;key;
  //delete the inorder successor
  root-&gt;right = deleteNode(root-&gt;right, temp-&gt;key);
  }
  return root;
  }
  //Function to count nodes in a BST using Morris Inorder traversal
  int counNodes(struct Node *root)
  {
  struct Node *current, *pre;
  int count =0;
  if(root == NULL)
      return count;
  current = root;
  while(current!=NULL)
  {
      if(current-&gt;left == NULL)
      {
          count++;
          current = current-&gt;right;;
      }
      else
      {
          pre = current-&gt;left;
          while(pre-&gt;right !=NULL &amp;&amp; pre-&gt;right !=current) 
          pre=pre-&gt;right;
          if(pre-&gt;right == NULL)
          {
              pre-&gt;right = current;
              current= current-&gt;left;
          }
          else
          {
              pre-&gt;right = NULL;
              count++;
              current = current-&gt;right;
          }
      }
  }
  return count;
  } 
  /*FUNCTION TO FIND MEDIAN */
  int FINDM(struct Node *root)
  {
  if(root == NULL)
      return 0;
      int count = counNodes(root);
      int currCount=0;
      struct Node *current = root, *pre, *prev;
      while(current !=NULL)
      {
          if(current-&gt;left == NULL)
          {
              currCount++;
              if(count%2!=0 &amp;&amp; currCount ==(count+1)/2)
                  return (prev-&gt;key);
                  //EVEN NUMBERS
                  else if(count%2==0 &amp;&amp; currCount==(count/2)+1)
                      return (prev-&gt;key + current-&gt;key)/2;
                      prev = current;
                      current = current-&gt;right;
                  }
                  else
                  {
                      pre=current-&gt;left;
                      while(pre-&gt;right !=NULL &amp;&amp; pre-&gt;right !=current)
                      pre= pre-&gt;right;
                      if(pre-&gt;right = NULL)
                      {
                          pre-&gt;right = current;
                          current = current-&gt;left;
                      }
                      else
                      {
                          pre-&gt;right = NULL;
                          prev = pre;
                          currCount++;
                          if(count%2!=0 &amp;&amp; currCount == (count+1)/2)
                              return (current-&gt;key);
      else if(count%2==0 &amp;&amp; currCount ==  (count/2)+1)
                                  return (prev-&gt;key+current-&gt;key)/2;
                                  prev = current;
                                  current = current-&gt;right;
                              }
                          }
                      }
                  }
  
    //Driver Program to test functions above
  int main()
  {
  // values are 28,90,0,32,56,78,212,34,62
  struct Node *root =NULL;
  
  root=insert(root,65);
  insert(root, 28);
  insert(root, 90);
  insert(root,0);
  insert(root, 32);
  insert(root,56);
  insert(root, 78);
  insert(root,212);
  insert(root,34);
  insert(root,62);
  
  printf("InOrder Traversal of Tree\n");
  inorder(root);
  
  printf("\nDelete 65!\n");
  root=deleteNode(root,65);
  printf("Modified Tree\n");
  inorder(root);
  
  printf("\nMEDIAN ");
  FINDM(root);
  return 0;
  }
  </code></pre>