I am trying to write the simplest version (uses less code lines) to write an iterative insert for binary search trees.
This what I did:
typedef struct Node {
int data;
struct Node* left;
struct Node* right;
} Node;
Node* insert_BST_it(Node* root, int v) {
Node* r = root, *hold, *node = create_node_bst(v);;
int left = 0;
while (r) {
left = 0;
if (elm <= r->data) {
hold = r;
r = r->left;
left = 1;
}
else {
hold = r;
r = r->right;
left = 0;
}
}
if (left)
hold->left = node;
else
hold->right = node;
return root;
}
How would you do a simpler one?
How would you do a simpler (iterative) one?
Node *, use a Node ** so we can easily update root if needed. IOWs, as code walks the tree, keep track of the address of the pointer that needs updating.Untested simpler code:
Node *insert_BST_it(Node *root, int val) {
Node **current = &root;
while (*current) {
current = (*current)->data <= val ? &(*current)->left : &(*current)->right;
}
*current = create_node_bst(val);
return root;
}
Sample usage:
Node *root = 0;
for (int i=0; i<3; i++) {
root = insert_BST_it(root, rand());
assert(root); // Test for insertion failure somehow.
}
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments