Thread: Binary search tree

Hello guys,

I was working with binary search tree and came up with the solution:

Code:

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

typedef struct data
{
        int  x;
        struct data *left;
        struct data *right;
}tree;

int main(void)
{
    tree  *root = NULL;
    tree  *current;
    int i,val;
    
    root = malloc(sizeof(tree));
    current = root;
    
    scanf(" %d",&val);
    current->x = val;
    
    current->left = NULL;
    current->right = NULL;
    
    for(i = 0; i < 5; i++)
    {
          scanf(" %d",&val);
          
          if(val <= current->x)
          {
                 current->left = malloc(sizeof(tree));
                 current = current->left;
                 current->x = val;
                 current->left = NULL;
                 current->right = NULL;
          }
          
          else if(val > current->x)
          {
                 current->right = malloc(sizeof(tree));
                 current = current->right;
                 current->x = val;
                 current->left = NULL;
                 current->right = NULL;
          }       
    }
    
}

Is the solution correct? Please help me out.

Is the solution correct? Please help me out.

Have you tested it?

I entered the code bellow it, to see if the value exists in the tree:

Code:

 follow = root;
    
    int s;
    printf("Enter a val: ");
    scanf(" %d",&s);
    
    int found = 0;
    while(follow)
    {
        if(s == follow->x)
        {
             found = 1;
        }
        
        if(s <= follow->x)
        {
             follow = follow->left;
        }
        
        if(s > follow->x)
        {
             follow = follow->right;
        }
    }
    
    printf("\n>>%d<<\n",found);
    system("pause");

After getting number from user, the program stops executing.

Originally Posted by iMalc

That's like a mechanic saying: "I was working with a car and came up with the following solution. Is the solution correct?"

I.e. We don't even know what you were trying to do with it, so of course we can't answer that.

What i was trying to do is, make a binary search tree, ask user for input 6 times, and then ask the user what number he would like to search for in the binary tree, if that number is found, store 1 in 'found' variable else leave a zero in it, that was assigned to it just after it had been initialized.

Your actual insert (the part inside the for loop) needs to have some sort of repetition, otherwise you can only insert nodes that are direct children of the root, you will never have grandchild nodes, etc. The tree will only contain at most 3 elements. You either need to use a recursive function to find the node to insert under, or a loop to move down the tree to the correct node to insert below, similar to what you did for your find function.

A few other things:
1. When you are describing a problem, give clear, concise and complete descriptions. If your program doesn't work, describe what doesn't work. Also provide us the input you gave the program, the incorrect output/behavior you seeing, and the correct output/behavior you expect to see.
2. Why limit the user to 6 inputs? Why not let them enter numbers until they're tired of it? The tree doesn't care, and the code is no more complex than a for loop of fixed size.
3. You should be checking the return value of scanf to make sure it actually read a number. If it fails, you need to clear the input buffer and ask again.
4. You should break your code up into functions. At the very least, I would have create_node, insert_node and find_node. Something like

Code:

// malloc's a new node, sets x to val and sets left and right to NULL.  Returns the newly malloc'd node
tree *create_node(int val)

// inserts node into the correct position in tree
void insert_node(tree *root, tree *node)

// finds the node containing val in tree.  Returns a pointer to the node if found, NULL otherwise
tree *find_node(tree *root, int val)

That last function I specified to return a pointer to the node if found. That way you can do something with the node if you want, or simply use a check for NULL to print if it exists:

Code:

tree *node = find_node(root, 42);
if (node) {
    printf("Found node containing 42\n");
}
else {
    printf("Sorry, could not find value in tree\n");
}