Binary Search Tree (BST) - Traversal search

Question

Write a function that, efficiently with respect to time used, returns 1 if a given binary search tree contains a given value, else 0.

For example, for the following tree:

n1 (Value: 1, Left: null, Right: null)
n2 (Value: 2, Left: n1, Right:n3)
n3 (Value: 3, Left: null, Right: null)

Call to contains(&n2, 3) should return 1 since a tree with root at n2 contains number 3.

The function should return 1, however, it returns 0 or nothing at all.

#include <stdlib.h>
#include <stdio.h>

typedef struct Node
{
    int value;
    struct Node *left;
    struct Node *right;
} Node;

int contains(const Node *root, int value)
{
    if (root->value == value)
    return 1;
    else if (value < root->value)
    {
        if (root->left == NULL)
        return 0;
        return contains(root->left, value);
    }
    else if (value > root->value)
    {
        if (root->right == NULL)
        return 0;
        return contains(root->left, value);
    }

}

int main()
{
    Node n1 = {.value=1, .left=NULL, .right=NULL};
    Node n3 = {.value=3, .left=NULL, .right=NULL};
    Node n2 = {.value=2, .left=&n1, .right=&n3};
    printf("%d", contains(&n2, 3));
}

At the second else if statment, you're checking root->left again. That should be contains(root->right, value). — kurtfu

shb shb · Accepted Answer · 2018-11-06T06:35:49

Are you not returning root->right, value when value > root->value?

else if (value < root->value)
        {
            if (root->left == NULL)
            return 0;
            return contains(root->left, value);
        }
        else if (value > root->value)
        {
            if (root->right == NULL)
            return 0;
            return contains(root->right, value); //You need to go to the right branch 
        }

Binary Search Tree (BST) - Traversal search

2 Answers