title: Red Black Tree implementation in C
body: <p>I have implemented Insertion part of Red black tree in C. However, I am not getting any output when I invoke DISPLAY function. I checked the functional correctness with BST implementation (some parts of RBT) and it is fine. Any help is appreciated.
      /* Implementing Red Black Trees according to CSLR*/</p>
  
  <pre><code>#include &lt;stdio.h&gt;
  #include &lt;stdlib.h&gt;
  
  struct rbtNode{
  int key;
  char color;
  struct rbtNode *left;
  struct rbtNode *right;
  struct rbtNode *parent;
  };
  
  struct rbtNode* root = NULL;
  
  void leftRotate(struct rbtNode *root,struct rbtNode *x){
  struct rbtNode *y;
  y = x-&gt;right;  //Set y
  x-&gt;right = y-&gt;left; // Turn y's left subtree into x's right subtree
  if( y-&gt;left != NULL){
      y-&gt;left-&gt;parent = x; //Bridge the y's left sublink
  }
  y-&gt;parent = x-&gt;parent; //Bridge x's old parent and y's parent
  if( x-&gt;parent == NULL){
      root = y;
  }
  else if( x-&gt;key == x-&gt;parent-&gt;left-&gt;key){
      x-&gt;parent-&gt;left = y; //Bridge x's old parent's left or right child
  }
  else x-&gt;parent-&gt;right = y;
  y-&gt;left = x; //put x on y's left
  x-&gt;parent = y; //Take care of x's parent
  
  return;
  }
  
  void rightRotate(struct rbtNode *root,struct rbtNode *y){
  struct rbtNode *x;
  x = y-&gt;left; //set x
  y-&gt;left = x-&gt;right; //Turn x's right subtree into y's left subtree
  if ( x-&gt;right != NULL){
      x-&gt;right-&gt;parent = y;
  }
  x-&gt;parent = y-&gt;parent; //Bridge y's old parent and x's parent
  if( y-&gt;parent == NULL){
      root = x;
  } 
  else if( y-&gt;key == y-&gt;parent-&gt;left-&gt;key){
      y-&gt;parent-&gt;left = x; //Bridge y's old parent's left or right child
  }
  else y-&gt;parent-&gt;right = x;
  x-&gt;right = y; //put y on x's right
  y-&gt;parent = x; //Take care of y's parent
  
  return;
  
  }
  
  void rbInsertFix(struct rbtNode *root,struct rbtNode *z){
  struct rbtNode *y;
  while (z-&gt;parent-&gt;color == 'r'){
      if (z-&gt;parent-&gt;key == z-&gt;parent-&gt;parent-&gt;left-&gt;key){
          y = z-&gt;parent-&gt;parent-&gt;right;
          if (y-&gt;color == 'r'){
              z-&gt;parent-&gt;color = 'b';
              y-&gt;color = 'b';
              z-&gt;parent-&gt;parent-&gt;color = 'r';
              z = z-&gt;parent-&gt;parent;
          }
          else if (z-&gt;key == z-&gt;parent-&gt;right-&gt;key){
              z = z-&gt;parent;
              leftRotate(root,z);
          }
          z-&gt;parent-&gt;color = 'b';
          z-&gt;parent-&gt;parent-&gt;color = 'r';
          rightRotate(root,z-&gt;parent-&gt;parent);
      }
      else {
          y = z-&gt;parent-&gt;parent-&gt;left;
          if (y-&gt;color == 'r'){
              z-&gt;parent-&gt;color = 'b';
              y-&gt;color = 'b';
              z-&gt;parent-&gt;parent-&gt;color = 'r';
              z = z-&gt;parent-&gt;parent;
          }
          else if (z-&gt;key == z-&gt;parent-&gt;left-&gt;key){
              z = z-&gt;parent;
              rightRotate(root,z);
          }
          z-&gt;parent-&gt;color = 'b';
          z-&gt;parent-&gt;parent-&gt;color = 'r';
          leftRotate(root,z-&gt;parent-&gt;parent);
      }
  }
  root-&gt;color = 'b';
  }
  
  void rbInsert(struct rbtNode *root, int val){
  struct rbtNode *z = (struct rbtNode*)malloc(sizeof(struct rbtNode));
  z-&gt;key = val;
  z-&gt;left = NULL;
  z-&gt;right = NULL;
  z-&gt;color = 'r';
  struct rbtNode *x = root;
  struct rbtNode *y;
  if ( root == NULL ){
      root = z;
      root-&gt;color = 'b';
      return;
  }
  while ( x != NULL){
      y = x;
      if ( z-&gt;key &lt; x-&gt;key){
          x = x-&gt;left;
      }
      else x = x-&gt;right;
  }
  z-&gt;parent = y;
  if ( y == NULL){
      root = z;
  }
  else if( z-&gt;key &lt; y-&gt;key ){
      y-&gt;left = z;
  }
  else y-&gt;right = z;
  rbInsertFix(root,z);
  
  return;
  }
  
  /*Display RBT - Inorder Traversal*/
  void inorderTree(struct rbtNode* root){
  struct rbtNode* temp = root;
  if (temp != NULL){
      inorderTree(temp-&gt;left);
      printf(" %d-%c ",temp-&gt;key,temp-&gt;color);
      inorderTree(temp-&gt;right);
  }
  return;
  }
  
  int main(int argc, char* argv[]){
  int loop = 1;
  while(loop){
      printf("\nRed Black Tree Management - Enter your choice : ");
      printf("\n1\tInsert into RBT\n2\tDisplay RBT inorder\n");
      int choice;
      int val;
      scanf("%d",&amp;choice);
      switch(choice){
          case 1:
          printf("\nEnter the integer you want to add : ");
          scanf("%d",&amp;val);
          rbInsert(root,val);
          break;
  
          case 2:
          printf("\nInorder tree traversal left-root-right\n");
          inorderTree(root);
          break;
  
          default:
          printf("\nInvalid Choice\n");
      }
      printf("\nPress '0' to terminate and '1' to continue : ");
      scanf("%d",&amp;loop);
  }
  
  return 0;
  }
  </code></pre>