Can't implement a recursion search in binary tree

Question

Here's my code:

  template <typename DataType> bool SearchValue(TreeNode<DataType> *root, DataType search_value)
{
    if(search_value != root->data)
    {
        if(root->right != NULL)
        {
            return SearchValue(root->right, search_value);
        }
        if (root->left != NULL)
        {
            return SearchValue(root->left, search_value);
        }
        return false;
    }
    else
    {
        return true;
    }
}

I can't make SearchValue function work properly. The condition is not to change the signature of SearchValue function. The problem is following: for example we try to find the element with data field equals "90" and it exists in the tree. Sometimes this code finds this element and sometimes not - depending on it's position in the tree. The question is how to make it work right every time.

I build the tree in such way:

template <typename DataType> TreeNode<DataType> *BuildTree()
{
    TreeNode<DataType> *root = new TreeNode<DataType>(10, new TreeNode<DataType>(20), new TreeNode<DataType>(30));

    TreeNode<DataType> *curRoot = root;
    curRoot = curRoot->left;
    curRoot->left = new TreeNode<DataType>(40);
    curRoot->left->left = new TreeNode<DataType>(70);
    curRoot->right = new TreeNode<DataType>(50);
    curRoot = curRoot->right;
    curRoot->left = new TreeNode<DataType>(80, new TreeNode<DataType>(100), new TreeNode<DataType>(110));
    curRoot = root->right;
    curRoot->left = new TreeNode<DataType>(60);
    curRoot = curRoot->left;
    curRoot->right = new TreeNode<DataType>(90, new TreeNode<DataType>(120), new TreeNode<DataType>(130));

    return root;
}

I test the search this way:

TreeNode<int> *treeRoot = BuildTree<int>();
    int valueToFind = treeRoot->data;
    cout << "Enter the value you'd like to find in the tree: ";
    cin >> valueToFind;
    cin.get();
    if(SearchValue(treeRoot, valueToFind) == true)
    {
        cout << "Value " << valueToFind << " was found!";
    }

The way I implement the tree:

template <typename DataType> struct TreeNode
{
    TreeNode(DataType val, TreeNode<DataType> *leftPtr = NULL, TreeNode<DataType> *rightPtr = NULL)
    {
        left = leftPtr;
        right = rightPtr;
        data = val;
    }
    TreeNode<DataType> *left, *right;
    DataType data;
};

Can you tell us the problem you've hit with your implementation? Examples would be nice. — dirkgently
– dirkgently, Commented Jun 3, 2012 at 13:31
-1 emilvikstrom.se/whyidownvote.html (What is your question? What have you tried?) — Emil Vikström
– Emil Vikström, Commented Jun 3, 2012 at 13:32

Mark Wilkins · Accepted Answer · 2012-06-03 13:32:40Z

5

The current search will always follow the right branch if it exists (and then never follow the left branch). If the data is ordered in the tree (which is typical), the code should examine the root node to make a decision on whether to traverse left or right.

answered Jun 3, 2012 at 13:32

Mark Wilkins

41.3k5 gold badges61 silver badges111 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Peter Alexander · Accepted Answer · 2012-06-03 14:09:10Z

1

Change

if(root->right != NULL)
{
    return SearchValue(root->right, search_value);
}
if (root->left != NULL)
{
    return SearchValue(root->left, search_value);
}
return false;

to

if(root->right != NULL)
{
    if (SearchValue(root->right, search_value))
        return true;
}
if (root->left != NULL)
{
    if (SearchValue(root->left, search_value))
        return true;
}
return false;

The way you currently have it, it will always go down the right branch and return if it was found there, never checking the left branch.

answered Jun 3, 2012 at 14:09

Peter Alexander

54.4k14 gold badges121 silver badges169 bronze badges

2 Comments

Puppy Over a year ago

This is O(n), kinda defeating the point of a binary tree, no?

Peter Alexander Over a year ago

@DeadMG: Not all binary trees are binary search trees. It doesn't look like a binary search tree (root's value is less than both its left and right value), so I've just solved the immediate problem he had. It actually looks like a binary min heap, so O(n) search would be correct.

Puppy · Accepted Answer · 2012-06-03 14:07:16Z

0

You can clearly tell that the code is wrong, because you never perform a comparison. Therefore, by default, the code cannot be correct.

You need to compare to decide which branch to go down, not simply test for existence.

answered Jun 3, 2012 at 14:07

Puppy

147k40 gold badges271 silver badges480 bronze badges

2 Comments

Sergey Shafiev Over a year ago

I can't agree with you, the comparison is represented by the following fragment: if(search_value != root->data)

Puppy Over a year ago

@Sergey: That's not a < comparison. That only tells you if you're there- not what direction to go in.

JsDoITao · Accepted Answer · 2012-06-03 14:21:24Z

0

Just as Peter Alexander said, you cannot return on right-branch, the only return condition is equal and return true, for else condition, need continue left-branches.

answered Jun 3, 2012 at 14:21

JsDoITao

1144 bronze badges

Collectives™ on Stack Overflow

Can't implement a recursion search in binary tree

4 Answers 4

Comments

2 Comments

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

2 Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related