This question has a follow up question:
Binary Search Tree insert while keeping track of parent for node to be added - iteration 2Binary 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?
