title: Red-Black Tree Deletion Partially Working
body: <p>I implemented a red black tree in c++ with find, insert and delete. The delete only works for right side nodes and for the root node. I can't figure out why it isn't working for any of the left side nodes. Here is my code:</p>
  
  <pre><code>Node* searchNode(Node* root, int value){
      Node* temp = root;
      while (temp != NULL){
          if (temp-&gt;val == value){
              return temp;
          }
          else if (temp-&gt;val &lt; value){
              temp = temp-&gt;right;
          }
          else if (temp-&gt;val &gt; value){
              temp = temp-&gt;left;
          }
      }
  }
  
  Node* sibling(Node* node){
      if ((node == NULL) || (node-&gt;parent == NULL)){
          return NULL;
      }
      if (node == node-&gt;parent-&gt;left){
          return node-&gt;parent-&gt;right;
      }
      else{
          return node-&gt;parent-&gt;left;
      }
  }
  Node* maxNode(Node* node){
      while (node-&gt;right != NULL){
          node = node-&gt;left;
      }
      return node;
  }
  void replaceNode(Node* old, Node* new_node){
      if (old-&gt;parent == NULL){
          old = new_node;
      }
      else{
          if (old == old-&gt;parent-&gt;left){
              old-&gt;parent-&gt;left = new_node;
          }
          else{
              old-&gt;parent-&gt;right = new_node;
          }
      }
      if (new_node != NULL){
          new_node-&gt;parent = old-&gt;parent;
      }
  }
  void deleteNode(Node* root, int value){
  
      Node* child;
      Node* temp = searchNode(root, value);
      if (temp == NULL){
          return;
      }
      if (temp-&gt;left != NULL&amp;&amp;temp-&gt;right != NULL){
          Node* pred = maxNode(temp-&gt;right);
          temp-&gt;val = pred-&gt;val;
          temp = pred;
      }
      if (temp-&gt;left == NULL || temp-&gt;right == NULL){
          if (temp-&gt;right == NULL &amp;&amp; temp-&gt;left == NULL){
              child = temp;
          }
          else if (temp-&gt;right == NULL){
              child = temp-&gt;left;
          }
          else{
              child = temp-&gt;right;
          }
      }
          if (temp-&gt;color == 1){
              temp-&gt;color = child-&gt;color;
              delete_case1(root, child);
          }
  
          replaceNode(temp, child);
          delete temp;
  
  }
  void delete_case6(Node* root, Node* n)
  {
      Node *s = sibling(n);
  
      s-&gt;color = n-&gt;parent-&gt;color;
      n-&gt;parent-&gt;color = 1;
  
      if (n == n-&gt;parent-&gt;left) {
          s-&gt;right-&gt;color = 1;
          rotate_left(root, n-&gt;parent);
      }
      else {
          s-&gt;left-&gt;color = 1;
          rotate_right(root, n-&gt;parent);
      }
  }
  void delete_case5(Node* root, Node* n)
  {
      Node *s = sibling(n);
  
      if (s-&gt;color == 1) {
          if ((n == n-&gt;parent-&gt;left) &amp;&amp;(s-&gt;right-&gt;color == 1) &amp;&amp;(s-&gt;left-&gt;color == 0)) {
              s-&gt;color = 0;
              s-&gt;left-&gt;color = 1;
              rotate_right(root, s);
          }else if ((n == n-&gt;parent-&gt;right) &amp;&amp;(s-&gt;left-&gt;color == 1) &amp;&amp;(s-&gt;right-&gt;color == 0)) {
              s-&gt;color = 0;
              s-&gt;right-&gt;color = 1;
              rotate_left(root, s);
          }
      }
      delete_case6(root, n);
  }
  void delete_case4(Node* root, Node* n)
  {
      Node *s = sibling(n);
  
          if ((n-&gt;parent-&gt;color == 0) &amp;&amp; (s-&gt;color == 1) &amp;&amp; (s-&gt;left-&gt;color == 1) &amp;&amp; (s-&gt;right-&gt;color == 1)) {
              s-&gt;color = 0;
              n-&gt;parent-&gt;color = 1;
          }
          else{
              delete_case5(root, n);
          }
  
      }
  void delete_case3(Node* root, Node* n){
      Node* s = sibling(n);
      if ((n-&gt;parent-&gt;color == 1) &amp;&amp;(s-&gt;color == 1) &amp;&amp;(s-&gt;left-&gt;color == 1) &amp;&amp;(s-&gt;right-&gt;color == 1)) {
          s-&gt;color = 0;
          delete_case1(root, n-&gt;parent);
      }
      else
          delete_case4(root, n);
  }
  void delete_case2(Node* root, Node* n){
      Node *s = sibling(n);
      if (s-&gt;color == 0){
          n-&gt;parent-&gt;color = 0;
          s-&gt;color = 1;
          if (n == n-&gt;parent-&gt;left){
              rotate_left(root, n-&gt;parent);
          }
          else if (n == n-&gt;parent-&gt;right){
              rotate_right(root, n-&gt;parent);
          }
      }
      delete_case3(root, n);
  }
  void delete_case1(Node* root,Node* n){
      if (n-&gt;parent != NULL){
          delete_case2(root,n);
      }
  }
  
  
  
  void main(){
      ABTree* ABtree=new ABTree;
      ABtree-&gt;root = NULL;
      insertTree(ABtree-&gt;root, 15);
      insertTree(ABtree-&gt;root, 8);
      insertTree(ABtree-&gt;root, 2);
      insertTree(ABtree-&gt;root, 9);
      insertTree(ABtree-&gt;root, 10);
      insertTree(ABtree-&gt;root, 12);
      insertTree(ABtree-&gt;root, 18);
      insertTree(ABtree-&gt;root, 25);
      insertTree(ABtree-&gt;root, 20);
      printTree(ABtree-&gt;root);
      Node* search=searchNode(ABtree-&gt;root, 18);
      cout &lt;&lt; endl;
      cout &lt;&lt; search-&gt;val&lt;&lt;endl;
      deleteNode(ABtree-&gt;root, 8);
      printTree(ABtree-&gt;root);
  }
  </code></pre>
  
  <p>For example if i want to delete either 8/9/2 the program crashes at delete_case4 at the if statement.</p>
  
  <p>Thanks in advance!</p>