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?

• Pimgd: Does your code work? You keep editing it. I'm worried because I wanted to review the code, but I'm not sure right now that I can.
• httpNick: Yes, sorry should be final edit @Pimgd
• Pimgd: I have rolled back the last edit. Please see what you may and may not do after receiving answers . Basically what happened is based on your code, you got an answer that says "don't use the check this way" but then you altered your code and their advice doesn't apply any more. But without the edits in revision 3 your code looks broken. I've opted to rollback to revision 3; in the future, try to test your code before posting, and do not edit the code once you have received any answers.
• Pimgd: I recommend accepting the answer given, applying their comments in your code, adding the other changes you've made and uploading as "Binary Search Tree insert while keeping track of parent for node to be added - iteration 2"
• httpNick: Itr 2 posted at : codereview.stackexchange.com/questions/121179/…

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.

• httpNick: Thanks for the reply on the styling. For point #1, I would not want to return NULL if n was NULL. For point #2, there is not a boolean type in C. Do you have another suggestion for changing the readability of the cmp variable? Edit: You just made me think of a crucial case I was missing though! If n is null I need to allocate a new node since that would be the case of the root.
• Piotr Aleksander Chmielowski: I forgot that there are no boolean :D Anyway, isGreater tells much more than cmp. I suggest rewriting this line in such way that is has two values: 1 or 0. Then you will be able to write: if (isGreater) and if(!isGreater)

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.