How can I search for an element in a binary tree that is not a bst?
This is an example of how my tree looks
1
/ \
2 3
/ \ / \
4 5 6 7
This is what I'm doing:
treeNode * find(treeNode *T, int x) {
if(T == NULL) return NULL;
if(x == T -> element) {
return T;
}
find(T -> left, x);
find(T -> right, x);
return NULL;
}
The problem is that the recursion does not stop when the if is satisfied
You're ignoring the return values from your recursive calls:
treeNode * find(treeNode *T, int x) {
if(T == NULL) return NULL;
if(x == T -> element) {
return T;
}
treeNode *result = find(T -> left, x);
if ( result ) // if the return value was found, this will not be NULL, so return the node
return result;
return find(T -> right, x); // will return NULL if its not found
}
You're missing return statements for your recursive calls. So not only does the recursion continue, but the value is never returned to the original caller.
treeNode * find(treeNode *T, int x) {
if(T == NULL) return NULL;
if(x == T -> element) {
return T;
}
auto findLeft = find(T -> left, x)
if (findLeft) return findLeft;
return find(T -> right, x);
}
In context to -
The problem is that the recursion does not stop when the if is satisfied
-the reason is because you must check if your recursive calls return a valid result and stop searching further.
Change -
find(T -> left, x);
find(T -> right, x);
-to something like -
treeNode* result = find(T -> left, x);
if (result != NULL)
return result;
return find(T -> right, x);
Look at the results of each attempt to find x
treeNode * find(treeNode *T, int x) {
if(T == NULL) return NULL;
if(x == T -> element) {
return T;
}
treeNode* result = find(T -> left, x);
if (result)
return result;
result = find(T -> right, x);
if (result)
return result;
return NULL;
}
ETA: the end of this can be simplified. Returning result if it's not NULL and returning NULL otherwise... is the same as returning result. All we're doing, really, is returning the value returned from the call to find. So...
treeNode * find(treeNode *T, int x) {
if(T == NULL) return NULL;
if(x == T -> element) {
return T;
}
treeNode* result = find(T -> left, x);
if (result)
return result;
return find(T -> right, x);
}
Binary trees are usually used to keep data sorted and quickly add/find items in that order.
Without order binary tree doesn't have many applications. So when I see your picture of tree I suspect that you have missed most important property of b-trees and probably important part of your task.
If you note that order is important in your task then take a look at that code:
class Node;
using NodePtr = std::uniqeu_ptr<Node>;
class Node
{
int value;
NodePtr left;
NodePtr right;
};
void insert(NodePtr &node, int value)
{
if (node) {
insert((value < node->value) ? node->left : node->right, value);
} else {
node.reset(new Node{value});
}
}
Node* find(Node* node, int value)
{
if (!node) {
return nullptr;
}
if (node->value == value) {
return node.get();
}
return find((value < node->value) ? node->left.get() : node->right.get(), value);
}
find, you should do something with the return values. That's how you detect a successful search, no?NULLunless it is already the searched for element.