CODEWITHSUNDEEP
c++visual-c++c++11
user1413188
user1413188

Reputation: 101

Inserting a node into a Binary Search Tree

I am trying to implement a simple C++ function that adds a node to a Binary Search Tree given the value of the node to be inserted, and the root of the BST.
Surprisingly, I am not able to push any element. Although I made sure that the statement where I am inserting the node is entered by the compiler, the tree did not have any of the nodes I am trying to add. I think the problem could be in how I am passing the node in the function argument. Anyone can help? Thank you. Here's my Node type and the implementation of the function. 

 struct Node{

    int value;
    Node *left;
    Node *right;
    };

    //this method adds a new node with value v to Binary Search Tree
    // node is initially the root of the tree
    void Push_To_BST(Node* node,int v)
    {

    // the right place to add the node
    if(node==NULL)
    {

    node=new Node();
    node->value= v;
    node->left= NULL;
    node->right=NULL;

    }

    //the value to be added is less than or equal the reached node
    else if(v <= node->value)
        {
    //adding the value to the left subtree
    Push_To_BST(node->left,v);
    }

    //the value to be added is greater than the reached node
    else if(v > node->value)
    {
    //adding the value to the right subtree
    Push_To_BST(node->right,v);
    }

    }

Upvotes: 0

Views: 4852

Answers (2)

Rook
Rook

Reputation: 6145

Careful with your referencing, there.

void Push_To_BST(Node* node,int v) 
{ 

// the right place to add the node 
if(node==NULL) 
{  
    node=new Node(); 
    // etc

The node you are allocating memory to is a local variable. You would need to pass in a Node** in order to pass out a pointer to a freshly created node.

Example:

void Push_To_BST(Node** pnode,int v) 
{ 
    Node* node = *pnode;

    // the right place to add the node 
    if(node==NULL) 
    {  
        node=new Node(); 
        // etc
    }
    else if(v < node->value)  
    {  
        //adding the value to the left subtree  
        Push_To_BST(&node->left,v);  
    }  
    // etc

and call it like

Node* n = new Node;
Push_To_BST(&n, 2);

Upvotes: 1

twalberg
twalberg

Reputation: 62369

You are allocating a new node and filling it in, but never changing a pointer in an existing node to point to the new node.

Upvotes: 0

Related Questions