Binary Search Tree insert while keeping track of parent for node to be added - iteration 2 Follow up question to
  Binary Search Tree insert while keeping track of parent for node to be added


I am implementing a red black tree for fun and am wondering how I should modify my basic BST insert. Note: this happens before the red black tree rules are applied, it just finds the correct place within the tree to add the node, places it, sets references, value and defaults the color to RED. I am mainly struggling to see if there may be a better way to tack on the parent reference for the newly added node. The implementation I have here looks ahead one step with a NULL check where a BST insert that does not need to track the parent would not need.

struct node * bstInsert(struct node *n, int x) {

  if (n != NULL) {

    int isGreater = (n-&gt;val &lt; x) ? -1 : (n-&gt;val &gt; x);

    if (isGreater == -1) {

      if (n-&gt;left == NULL) {
        n-&gt;left = createAChild(n, n-&gt;left, x);
      } else {
        bstInsert(n-&gt;left, x);
      }

    } else if (isGreater == 1) {

      if (n-&gt;right == NULL) {
        n-&gt;right = createAChild(n, n-&gt;right, x);
      } else {
        bstInsert(n-&gt;right, x);
      }

    }

  } else{

    n = createAChild(NULL, n, x);

  }

  return n;
}

struct node * createAChild(struct node *par, struct node *n, int x) {

  n = malloc(
    sizeof(struct node)
  );
  n-&gt;parent = par;
  n-&gt;left = n-&gt;right = NULL;
  n-&gt;val = x;
  n-&gt;color = RED;

  return n;

}


Is there a cleaner solution to setting the parent reference for the node to be added?
You should check the result given by malloc, because otherwise your program may crash. Maybe not on your system right now, but basically, memory allocation can fail, and if it does, your program will crash afterwards by dereferencing a null pointer.

Additionally, your createAChild function should not take a node pointer. What happens if I pass in an existing object? You just overwrite it. That's a cause for memory leaks. Treat createAChild as a constructor: either give it a cleanly allocated node struct, or let it allocate its own struct.