Binary Search Tree

Question

so i coded a binary search tree in C which looks with this struct:

struct tnode {
    int content;
    struct tnode *left; /* left tree part */
    struct tnode *right; /* right tree part */
};

My main method:

int main() {

    struct tnode *Baum = NULL;
    struct tnode *tmpPos = NULL;
    Baum = addelement (Baum, 32);
    Baum = addelement(Baum, 50);
    Baum = addelement(Baum, 60);
    tmpPos = searchnode(Baum,50);
}

So basicly this creates me a Binary search tree with 3 elements (32,50,60). My searchnode method is supposed to move a pointer to the "50" so i can delete it afterwards. However my searchnode Method only returns the pointer if the element im searching is the root of my binary search tree.

searchnode:

struct tnode *searchnode(struct tnode *p, int nodtodelete) {
    if (p == NULL) {
        printf("Baum ist leer oder Element nicht vorhanden \n");
    }

    if ( p -> content == nodtodelete) {
        return p;
    }

    if (p->content > nodtodelete) {
        searchnode (p->right, p->content);
    }
    if (p->content < nodtodelete) {
        searchnode(p->left, p->content);
    }
}

Maybe you guys can help me.

Don't you have the left/right subtree decisions reversed? if (p->content > nodtodelete) you should be taking the left path. — Weather Vane
– Weather Vane, Commented Jul 14, 2016 at 18:35
Welcome to the site! Check out the tour for more about asking questions that will attract quality answers. Have you already confirmed that addelement() works correctly? — cxw
– cxw, Commented Jul 14, 2016 at 18:35
Please don't change the question after answers has been posted. Ask a new question if you have one. stackoverflow.com/questions/ask — 2501
– 2501, Commented Jul 14, 2016 at 19:47

R Sahu · Accepted Answer · 2016-07-14 18:46:31Z

2

Your function has undefined behavior since it doesn't have any return statements in the recursive calls.

Also, the recursive calls need to be fixed to use the right input.

struct tnode *searchnode(struct tnode *p, int nodtodelete)
{
   if (p == NULL)
   {
      printf("Baum ist leer oder Element nicht vorhanden \n");
      return NULL;
   }

   if ( p -> content == nodtodelete)
   {
      return p;
   }

   // This is copied from OP's question but it seems suspect.
   // It should probably be:
   // if (p->content < nodtodelete)
   if (p->content > nodtodelete)
   {
      return searchnode (p->right, nodtodelete);
   }

   return searchnode(p->left, nodtodelete);
}

edited Jul 14, 2016 at 18:46

answered Jul 14, 2016 at 18:43

R Sahu

207k15 gold badges168 silver badges291 bronze badges

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

4 Comments

Robin Schmidt Over a year ago

Posted an aswer with another question related to the Binary Search tree, maybe you can spot the mistake here aswell.

R Sahu Over a year ago

@RobinSchmidt, please post another question instead of asking another question in an answer.

Weather Vane Over a year ago

@RSahu -Is left/right decision reversed? -uh you commented that!

R Sahu Over a year ago

@WeatherVane, Yes, I think it is reversed.

R Sahu · Accepted Answer · 2016-07-14 18:39:46Z

2

You should pass the value you're searching for, not the value of the node:

searchnode (p->right, nodtodelete);
                      ^

Make the same change to the other recursive call.

searchnode(p->left, nodtodelete);

edited Jul 14, 2016 at 18:39

R Sahu

207k15 gold badges168 silver badges291 bronze badges

answered Jul 14, 2016 at 18:36

2501

25.8k4 gold badges51 silver badges93 bronze badges

Collectives™ on Stack Overflow

Binary Search Tree

2 Answers 2

4 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related