1
\$\begingroup\$

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

    if (isGreater == -1) {

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

    } else if (isGreater == 1) {

      if (n->right == NULL) {
        n->right = createAChild(n, n->right, x);
      } else {
        bstInsert(n->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->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?

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ One question about checking malloc: If malloc fails, what would be an appropriate handler? I am not familiar enough with C to come up with something at the moment. \$\endgroup\$ – httpNick Feb 26 '16 at 10:37
  • \$\begingroup\$ @httpNick Return null, treating the insertion as a failure. \$\endgroup\$ – Pimgd Feb 26 '16 at 11:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.