CODEWITHSUNDEEP
c++data-structuresbinary-tree
Astros
Astros

Reputation: 179

Find an element in a binary tree

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

Upvotes: 0

Views: 1013

Answers (5)

Marek R
Marek R

Reputation: 37697

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);
}

Upvotes: 0

Tim Randall
Tim Randall

Reputation: 4145

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);
}

Upvotes: 2

Happy Green Kid Naps
Happy Green Kid Naps

Reputation: 1673

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);

Upvotes: 2

junvar
junvar

Reputation: 11574

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);
}

Upvotes: 3

ChrisMM
ChrisMM

Reputation: 10022

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
}

Upvotes: 3

Related Questions