CODEWITHSUNDEEP
c++recursionbinary-tree
Sergey Shafiev
Sergey Shafiev

Reputation: 4375

Can't implement a recursion search in binary tree

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

Upvotes: 0

Views: 203

Answers (4)

JsDoITao
JsDoITao

Reputation: 114

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.

Upvotes: 0

Peter Alexander
Peter Alexander

Reputation: 54270

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.

Upvotes: 1

Puppy
Puppy

Reputation: 146930

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.

Upvotes: 0

Mark Wilkins
Mark Wilkins

Reputation: 41222

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.

Upvotes: 5

Related Questions