Binary Search Tree (BST) - поиск обхода

Question

Напишите функцию, которая эффективно по используемому времени возвращает 1, если заданное двоичное дерево поиска содержит заданное значение, иначе 0.

Например, для следующего дерева:

• n1 (значение: 1, слева: ноль, справа: ноль)
• n2 (значение: 2, слева: n1, справа: n3)
• n3 (значение: 3, слева: ноль, справа: ноль)

Вызов содержимого (& n2, 3) должен возвращать 1, поскольку дерево с корнем в n2 содержит число 3.

Функция должна возвращать 1, однако возвращает 0 или вообще ничего.

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

Answer 1

В другом состоянии вы идете не к правой ветви, а к левой.

else if (value > root->value)
{
    if (root->right == NULL)
    return 0;
    return contains(root->left, value);
}

Используйте строку ниже в случае, если значение больше, чтобы исправить

    return contains(root->right, value);

Answer 2

Вы не возвращаете root->right, value, когда 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 
        }