Im working on a Binary Search Tree assignment for class and for this function I need to follow my professor's pseudo code. Unfortunately, I'm not sure about one specific detail, and she refuses to clarify.
Link to the pseudo code is here: https://i.sstatic.net/Rit7e.jpg
SUBROUTINE insert(current, parent, node)
IF current is null
IF parent is null
root = node
ELSE
ID node.value < parent.value
parent.left = node
ELSE
parent.right = node
END IF
RETURN true
END IF
ELSE IF node.value = current.=value
RETURN false
ELSE IF ode.value < current.value
insert(current.left, current, node)
ELSE
insert(current.right, current, node)
END IF
END SUBROUTINE
In place of node, I've tried seemingly most of the allowed variables, including current, parent, (and even value, which didn't work. Shocker.)
bool recursiveInsert(Node* current, Node* parent, double value)
{
if (current == NULL)
{
if (parent == NULL)
{
}
else
{
if (current->value < parent->value)
{
parent->left = current;
}
else
{
parent->right = current;
}
return true;
}
}
else if(parent->value == current->value)
{
return false;
}
else if (parent->value < current->value)
{
insert(current->left, current->value, current);
}
else
{
insert(current->right, current->value, current);
}
}
I expect the output to add the value to the binary search tree and return true, but the program currently just throws a error whenever I get to the parts that require "node".
node in the context of the pseudocode is a previously allocated node containing the data being inserted into the tree. The initial caller allocates it (which is both pointless and never done in RW code).In reality, it is highly unlikely to actually do this pattern unless you're considering a library that potentially moves nodes out of one tree into another, and you want to avoid the expense of setting-up/tearing-down the nodes themselves.
Regarding the algorithm, it's fairly straightforward, though not very pretty:
If both current and parent are null, it means this must be the first node in the tree tracked by some global pointer root. Therefore, root is assigned the incoming node directly.
Otherwise, If current is null but parent is not if means parent is some potential leaf in the tree (meaning it has either a left, a right, or both contained pointers that are null), and you've landed on the null pointer. The insertion requires comparing against the parent value to know whether you hang the node on the left or the right. Note that this is inefficient, as you already did this comparison (it's how you got here in the first place).
Otherwise if current is not-null we simply check whether the values are equal, or less (greater is assumed if neither of those are true), and drive into the subtree of left or right if warranted. In that case, current.left or current.right become the recursed current, and current becomes the parent of said-same recursive call.
That's it. That's how that algorithm works. And frankly, it's marginal.
To implement this algorithm with your argument list (that takes a value rather than a node for the final argument), you need only ensure node allocation only happens when it is time to actually hang it, and only then (there are two such cases.
bool recursiveInsert(Node* current, Node* parent, double value)
{
bool result = false;
if (current == NULL)
{
if (parent == NULL)
{
root = malloc(sizeof *root);
root->value = value;
root->left = root->right = NULL;
}
else
{
Node *p = malloc(sizeof *p);
p->value = value;
p->left = p->right = NULL;
if (value < parent->value)
{
parent->left = p;
}
else
{
parent->right = p;
}
result = true;
}
}
else if (value < parent->value)
result = recursiveInsert(current->left, current, value);
else if (parent->value < value)
result = recursiveInsert(current->right, current, value);
return result;
}
When inserting a value into the tree, the call will look something like this:
recursiveInsert(root, NULL, value);
It's not pretty, but it works. That it relies on global root presence is probably the worst part of this algorithm. The multi-compare is probably second on the list of yuck.
Ideally the root of the tree is passed in as an argument. Further, we can make the algorithm recursive as it is now, but no longer rely on some global root. Finally, we can reduce the argument count to two: the address of a pointer (initially the address of the root pointer), and the value being inserted. sing a pointer-to-pointer as the tree access method makes this algorithm elegant, whether using recursion or not. Both are provided below:
bool treeInsert(Node **pp, double value)
{
bool result = false;
if (!*pp)
{
*pp = malloc(sizeof **pp);
(*pp)->value = value;
(*pp)->left = (*pp)->right = NULL;
result = true;
}
else if (value < (*pp)->value)
{
result = recursiveInsert(&(*pp)->left, value);
}
else if ((*pp)->value < value)
{
result = recursiveInsert(&(*pp)->right, value);
}
return result;
}
bool treeInsert(Node **pp, double value)
{
bool result = false;
while (*pp)
{
if (value < (*pp)->value)
pp = &(*pp)->left;
else if ((*pp)->value < value)
pp = &(*pp)->right;
else break;
}
if (!*pp)
{
*pp = malloc(sizeof **pp);
(*pp)->value = value;
(*pp)->left = (*pp)->right = NULL;
result = true;
}
return result;
}
in either case, you invoke by passing the address of the root pointer (thus a pointer to pointer), where an empty try is signified by a NULL root:
treeInsert(&root, value);
Either function will accomplish the task at hand. I leave the error-hardening asa task for you (check your mallocs).