C++ Binary Search Tree Insert Implementation

Question

I'm trying to build a function to insert into a binary search tree, but I'm having a hard time figuring out why it won't work. I understand fundamentally how the function is supposed to work, but based on the template I was given it seems as though I am to avoid creating a BST class but instead rely on the Node class and build the desired functions to work on that. Here's the given template:

#include <iostream>
#include <cstddef>

using std::cout;
using std::endl;

class Node {
    int value;
public:
    Node* left;       // left child
    Node* right;      // right child
    Node* p;          // parent
    Node(int data) {
        value = data;
        left = NULL;
        right = NULL;
        p  = NULL;
    }
    ~Node() {
    }
    int d() {
        return value;
    }
    void print() {
        std::cout << value << std::endl;
    }
};

function insert(Node *insert_node, Node *tree_root){
    //Your code here
}

The issue I'm having is when I implement the following code, where getValue is a simple getter method for Node:

int main(int argc, const char * argv[]) {
     Node* root = NULL;
     Node* a = new Node(2);
     insert(a, root);
}

void insert(Node *insert_node, Node *tree_root){
    if (tree_root == NULL)      
        tree_root = new Node(insert_node->getValue());

The code appears to compile and run without error, but if I run another check on root after this, it returns NULL. Any idea what I'm missing here? Why is it not replacing root with a new node equal to that of insert_node?

I also realize this doesn't appear to be the optimal way to implement a BST, but I am trying to work with the template given to me. Any advice would be appreciated.

Search for and read about passing arguments by reference in c++. — Some programmer dude
Even better void insert(std::unique_ptr<Node> insert_node, std::unique_ptr<Node>& tree_root). — Jarod42
@Jarod42, thanks for the input! What makes that second version even better? — Brendan
Smart pointers allow to not manually handle memory. So you would have no memory leak in your example with std::unique_ptr. — Jarod42

Nikita Nikita · Accepted Answer · 2016-09-09T19:30:31

As Joachim said your issue relates to difference between passing parameter by reference and by value.

In your code void insert(Node *insert_node, Node *tree_root) you pass Node* tree_root by value. Inside the function you change local copy of this pointer, so outer value is not changed.

To fix it you should pass Node* tree_root by reference. Parameter declaration can be Node*& tree_root (or Node** tree_root). E.g:

void insert(Node* insert_node, Node*& tree_root){
    if (tree_root == NULL)      
        tree_root = new Node(insert_node->getValue());

C++ Binary Search Tree Insert Implementation

1 Answers