pointers - C++ Binary Search Tree Insertion functions -

helly everyone,

i took c++ coding course practically no prior knowledge(my understanding of pointers still shakey)at university semester. have implement binary search tree in c++ , problem follows: on predefined node structure values , pointers left , right node supposed implement several functions, 2 of them being:

void insertnode(node* root, node* node) 

which supposed fit handed node given tree "root", , 1 called

void insertvalue(node* root, int value) 

which should create new instance of node struct passed value , fit in given tree "root". supposed use both createnode (simple function create node* pointer of new node instance int value , left/right pointers set null) , insertnode.

im kind of running in treadmill here , dont think understand how functions supposed work(eg. difference between them). yesterday wrote function:

void insertnode(node* root, node* node){     if(root == null){         root = createnode(node->value);     }     else if(root->value < node->value){         if(node->left != null){              insertnode(root, node->left);         }         else{              node->left = createnode(root->value);         }     }     else if(root->value > node->value){         if(node->right != null){              insertnode(root, node->right);         }         else{             node->right = createnode(root->value);         }     } } 

since im not able test these functions without later functions build tree given nodes curious if here next functions insertvalue(what supposed insertnode doesnt already? :s)

greetings , in advance.

initial note: answer assumes insertnode function called root being root of tree, , node being node insert tree.

---

one problem statement:

root = createnode(node->value); 

since argument root passed value, means copied, assignment change local copy. once function returns original pointer pass function not have changed.

you need pass pointer by reference, meaning root argument references original variable passed in function, instead of being copied. using ampersand when declaring argument:

node*& root 

the above means root reference pointer node.

so complete insertnode declaration should like

void insertnode(node*& root, node* node) 

---

there other problems, example these lines not correct:

if(node->left != null){      insertnode(root, node->left); } else{      node->left = createnode(root->value); } 

this not correct because node->left should null always, makes create new node using value root of tree, , assign node->left, never insert node in tree.

what should instead simply

insertnode(node->left, node); 

of course should same change setting right branch.

---

combining 2 solutions above, function like

void insertnode(node*& root, node* node) {     if (root == 0)         root = node;     else if (root->value < node->value)         insertnode(root->left, node);     else         insertnode(root->right, node); } 

this function solves third problem current code: if node->value equal root->value? above function puts in right branch.