Binary Tree insert Func

[nslice22]

I am having trouble writing an insert function for a binary tree.

Here is the structure that I have to use.

I have the print function done, the insert function is the one I am having trouble with, thanks a lot.

typedef struct bt_{ 
int value; 
struct bt_ *right; 
struct bt_ *left; 
}BST; 





BST* insert(BST* root, int value); 
/*This function will insert a new node with a value of value in BST. Remember, in this program a binary tree is defined either being null or it is a node whose left subtree is filled with nodes whose values are less than its own, and a right subtree whose right subtree is filled with nodes whose values are greater than or equal to its own. Although not required, it is recommended that you try and implement this function recursively. */ 


void printTree(BST* root) 
{ 
displayBST(root, 0); 
} 

void displayBST(BST* root, int depth) 
{ 
if (root == NULL) 
{ 
padding(' ', depth); 
printf("-\n"); 
return; 
} 

displayBST(root->left, depth+4); 
padding(' ', depth); 
printf("%d\n", root->value); 
displayBST(root->right, depth+4); 
} 

void padding(char toPrint, int numTimes) 
{ 
int i; 
for (i = 0; i < numTimes; i++) 
printf("%c", toPrint); 
}

Thanks for your help!

[anduril462]

So, you know how to apply recursion to an in-order traversal to print the tree, by treating the left and right sub-trees as effectively just a smaller binary tree. Can you apply that concept to inserting a node/value? If the node is smaller than the root of this subtree, what might you do? What if it's bigger? What if it's equal? What if root is null?

I'm having a hard time figuring out how to give help without just giving away the answer. See if you can at least post some attempt in pseudo code or actual code with your attempt, and we can guide you from there.

[nslice22]

So, you know how to apply recursion to an in-order traversal to print the tree, by treating the left and right sub-trees as effectively just a smaller binary tree. Can you apply that concept to inserting a node/value? If the node is smaller than the root of this subtree, what might you do? What if it's bigger? What if it's equal? What if root is null?

I'm having a hard time figuring out how to give help without just giving away the answer. See if you can at least post some attempt in pseudo code or actual code with your attempt, and we can guide you from there.

Here is my attempt:

BST * insert( BST * root, int value ) { 
    if ( root != 0 ) { 
        if ( value < root->value ) 
            root->left= insert( root->left, value ); 
        else if ( value > root->value ) 
            root->right= insert( root->right, value ); 
        return root; 
    } 
    BST *n= (BST *) malloc( sizeof( BST ) ); 
    n->value= value; 
    n->left= n->right= 0; 
    return n; 
} 

[anduril462]

That looks about right. Test it. If it gives you trouble, post back here with the input you used that failed and a description of the problem.

[nslice22]

That looks about right. Test it. If it gives you trouble, post back here with the input you used that failed and a description of the problem.

Here are the errors

prel.c: In function ‘displayBST’:
prel.c:53: warning: passing argument 1 of ‘padding’ makes integer from pointer without a cast
prel.c:13: note: expected ‘char’ but argument is of type ‘char *’
prel.c:58: warning: passing argument 1 of ‘padding’ makes integer from pointer without a cast
prel.c:13: note: expected ‘char’ but argument is of type ‘char *’


Here is my code:

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


typedef struct bt_{
        int value;
        struct bt_ *right;
        struct bt_ *left;
}BST;


BST* insert(BST* root, int value);
void printTree(BST* root);
void displayBST(BST* root, int depth);
void padding(char toPrint, int numTimes);


int main(){


        int value;
        BST *new_BST;


        while(value != -1){
                printf("\nEnter a number to put into the tree");
                scanf("%d", &value);


                new_BST = insert(new_BST, value);
        }


        printTree(new_BST);
}


BST* insert(BST* root, int value){
        if(root != 0){
                if(value < root->value)
                        root->left = insert(root->left, value);
                else if( value > root->value)
                        root->right = insert(root->right, value);
                return root;
        }
        BST *n = (BST*) malloc(sizeof(BST));
        n->value = value;
        n->left = n->right = 0;
        return n;
}


void printTree(BST* root)
{
        displayBST(root,0);

void displayBST(BST* root, int depth){


        if(root==NULL)
        {
                padding("''", depth);
                printf("-\n");
                return;
        }
        displayBST(root->left,depth+4);
        padding("'' ", depth);
        printf("%d\n", root->value);
        displayBST(root->right, depth+4);
        }
void padding(char toPrint, int numTimes)
{
        int i;
        for(i=0; i < numTimes; i++)
                printf("%c", toPrint);
}

thanks

[anduril462]

What you used to have that worked

padding(' ', depth);

What you now have, that doesn't work

padding("'' ", depth);

[nslice22]

What you used to have that worked

padding(' ', depth);

What you now have, that doesn't work

padding("'' ", depth);

okay thanks it works now. How would I go about searching the list? and maybe deleting a number in the list? Thanks a lot lol.

[anduril462]

Well, searching is easy, because of the structure and organization of the binary tree.

As for deleting, well, there's a nice Wikipedia article that talks about binary trees and the various operations on them. I would hate to rob you of the wonderful learning experience by just telling you how to do it .

[nslice22]

Well, searching is easy, because of the structure and organization of the binary tree.

As for deleting, well, there's a nice Wikipedia article that talks about binary trees and the various operations on them. I would hate to rob you of the wonderful learning experience by just telling you how to do it .

I know, but it would be sweet if you could help me out just this once, if not its cool thanks for everything

[anduril462]

I know, but it would be sweet if you could help me out just this once, if not its cool thanks for everything

Giving you the solution would be the exact opposite of sweet, and it would do the exact opposite of helping you out.

1. It would violate the forum's homework policy. I know you know that, since you agreed to having read the forum rules and to abiding by them, as a requirement to signing up for your account.
2. It would violate my personal ethics.
3. It would encourage you to try this tactic again, either with me or somebody else, since it worked once.
4. It would encourage you to try this tactic again, because you never learned the fundamentals, so you can't do the advanced work yourself, even if you wanted to.
5. Helping you cheat your way to a degree you don't deserve means you might get a job you don't deserve and aren't qualified for. I don't want to do anything to increase the number of incompetent people that work in the programming industry. One way or another, it will make my life more difficult, whether I rely on them as employees, they make a product I use, etc.
6. The mere fact that you asked does not reflect well on your character.

Yep, I'm a giant a-hole when it comes to academic honesty and ethics. Other than that, I'm a pretty nice guy. If you make a real attempt and post back with real questions, you'll get real help instead of snark.

Seriously though, the search is super easy. Think about how you find a node. Draw a tree on paper and do the lookup by hand. The delete is trickier but still isn't that hard, once you take a little time to study it. Again, draw a few examples out on paper and work through them by hand. I told you in your Linked List thread to work out a solution by hand -- that goes for all your programming problems. I can not stress this enough: if you can't solve the problem yourself, you can't program a computer to solve it.

[nslice22]

Giving you the solution would be the exact opposite of sweet, and it would do the exact opposite of helping you out.

1. It would violate the forum's homework policy. I know you know that, since you agreed to having read the forum rules and to abiding by them, as a requirement to signing up for your account.
2. It would violate my personal ethics.
3. It would encourage you to try this tactic again, either with me or somebody else, since it worked once.
4. It would encourage you to try this tactic again, because you never learned the fundamentals, so you can't do the advanced work yourself, even if you wanted to.
5. Helping you cheat your way to a degree you don't deserve means you might get a job you don't deserve and aren't qualified for. I don't want to do anything to increase the number of incompetent people that work in the programming industry. One way or another, it will make my life more difficult, whether I rely on them as employees, they make a product I use, etc.
6. The mere fact that you asked does not reflect well on your character.

Yep, I'm a giant a-hole when it comes to academic honesty and ethics. Other than that, I'm a pretty nice guy. If you make a real attempt and post back with real questions, you'll get real help instead of snark.

Seriously though, the search is super easy. Think about how you find a node. Draw a tree on paper and do the lookup by hand. The delete is trickier but still isn't that hard, once you take a little time to study it. Again, draw a few examples out on paper and work through them by hand. I told you in your Linked List thread to work out a solution by hand -- that goes for all your programming problems. I can not stress this enough: if you can't solve the problem yourself, you can't program a computer to solve it.

Thanks a lot