Binary Search Tree insert while keeping track of parent for node to be added

Question

This question has a follow up question:
Binary Search Tree insert while keeping track of parent for node to be added - iteration 2

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 cmp = (n->val < x) ? -1 : (n->val > x);

    if (cmp == -1) {

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

    } else if (cmp > 0) {

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

    }

  }

  return n;
}

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

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

  return n;

}

Is there a cleaner solution to setting the parent reference for the node to be added?

Answer 1

1. Instead of if (n != NULL) and then indenting the whole code of function, it is better to write: if (n == NULL) { return NULL; }

2. The line int cmp = (n->val < x) ? -1 : (n->val > x); is very hard to read. I suggest finding a better name to cmp - for example isGreater and changing its type to boolean.

Answer 2

Problems with your code:

struct node * bstInsert(struct node *n, int x) {
    if (n != NULL) {

what if n is null, e.g an empty tree? How does your tree get started if you can't insert anything in it when it is empty?

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

Why are you passing in n here? You don't use that variable afaict. You can easily change the signature to struct node * createAChild(struct node *par, int x).

Anyways, your insert can be made better by using a pointer-pointer!

struct node * bstInsert(struct node *n, int x) {
    struct node **addr = &n;        
    struct node *parent = NULL;
    // If tree is empty, this whole loop is skipped.
    while(*addr) {
        parent = *addr;
        // Left branch is value is less than, otherwise right branch.
        if (n->val < x) {
            addr = &parent->left;
        } else {
            addr = &parent->right;
        }
        // Here parent points to a node struct and addr points to 
        // the left or right field of it. If that field is NULL, 
        // we have found our insertion point.
    }
    *addr = createAChild(parent, x);
    return n;
}

I also recommend you train your ability in converting recursive searches in bst trees to iterative ones using while loops. It is good practice.