Ykhjuy

I have an implementation for my first binary search tree in C++. I was wondering if there was some cleaner way to avoid using the double pointer in the way I have my code setup? Such as on one line I have:

(*node)->left = insert(&((*node)->left),value);

Which seems a bit "messy", but it almost seems necessary for the way I have implemented the BST. Maybe I am possibly missing a way I can change the syntax slightly to achieve the same result? I understand that I can have a double pointer as a parameter for my functions, but I have been told that it is not the standard in C++. I have my code posted below, along with how I am testing it.I am trying to prepare for technical interviews so any feedback is welcome.

#include<stdio.h> 

#include<stdlib.h> 

#include<iostream>

struct Node 

{ 

    int data; 

    Node *left, *right; 

}; 



// A utility function to create a new BST node 

Node* newNode(int data) 

{ 

    Node *temp =  new Node(); 

    temp->data = data; 

    temp->left = NULL; 

    temp->right = NULL; 

    return temp; 

} 



// A utility function to do inorder traversal of BST 

void inorder(Node **root) 

{ 

    if (*root != NULL) 

    { 

        inorder(&((*root)->left)); 

        printf("%d n", (*root)->data); 

        inorder(&((*root)->right)); 

    } 

} 



/* A utility function to insert a new node with given key in BST */

Node* insert(Node** node, int value) 

{ 

    if(*node==NULL){

        return newNode(value);

    }

    if((*node)->data > value){

        (*node)->left = insert(&((*node)->left),value);

    }

    else if((*node)->data < value){

        (*node)->right = insert(&((*node)->right),value);

    }

    return *node;

} 



// Driver Program to test above functions 

int main() 

{ 

    /* Let us create following BST 

              50 

           /      

          30      70 

         /      /   

       20   40  60   80 */

    Node *root = NULL; 

    root = insert(&root, 50); 

    insert(&root, 30); 

    insert(&root, 20); 

    insert(&root, 40); 

    insert(&root, 70); 

    insert(&root, 60); 

    insert(&root, 80); 



    // print inoder traversal of the BST 

    inorder(&root); 



    return 0; 

} 

EDIT:
By changing " ** " in the parameters of the function to "*&" was able to make code much easier to read, with the same functionality.

#include<stdio.h> 

#include<stdlib.h> 

#include<iostream>

struct Node 

{ 

    int data; 

    Node *left, *right; 

}; 



// A utility function to create a new BST node 

Node* newNode(int data) 

{ 

    Node *temp =  new Node(); 

    temp->data = data; 

    temp->left = NULL; 

    temp->right = NULL; 

    return temp; 

} 



// A utility function to do inorder traversal of BST 

void inorder(Node *&root) 

{ 

    if (root != NULL) 

    { 

        inorder(((root)->left)); 

        printf("%d n", (root)->data); 

        inorder(((root)->right)); 

    } 

} 



/* A utility function to insert a new node with given key in BST */

Node* insert(Node*& node, int value) 

{ 

    if(node==NULL){

        return newNode(value);

    }

    if((node)->data > value){

        node->left = insert(((node)->left),value);

    }

    else if((node)->data < value){

        (node)->right = insert(((node)->right),value);

    }

    return node;

} 



// Driver Program to test above functions 

int main() 

{ 

    /* following BST 

              50 

           /      

          30      70 

         /      /   

       20   40  60   80 */

    Node *root = NULL; 

    root = insert(root, 50); 

    insert(root, 30); 

    insert(root, 20); 

    insert(root, 40); 

    insert(root, 70); 

    insert(root, 60); 

    insert(root, 80); 



    // print inoder traversal of the BST 

    inorder(root); 



    return 0; 

}

If you're trying to learn C++, you should get comfortable with constructors and destructors — they're what C++ is all about!

struct Node 

{ 

    int data; 

    Node *left, *right; 

}; 



// A utility function to create a new BST node 

Node* newNode(int data) 

{ 

    Node *temp =  new Node(); 

    temp->data = data; 

    temp->left = NULL; 

    temp->right = NULL; 

    return temp; 

}

That's C style. C++ style would be:

struct Node { 

    int data_; 

    Node *left_ = nullptr;

    Node *right_ = nullptr;



    explicit Node(int data) : data_(data) {}

}; 

Then when you want a new heap-allocated node, you don't call newNode(42) — you call new Node(42)! Or, a good habit you should get into: call std::make_unique<Node>(42) to get back a smart pointer.

Notice that I added sigils to your data members (data_ etc) to distinguish them from non-member variables; and I declared no more than one variable per line to reduce reader confusion.

void inorder(Node *&root) 

{ 

    if (root != NULL) 

    { 

        inorder(((root)->left)); 

        printf("%d n", (root)->data); 

        inorder(((root)->right)); 

    } 

}

Several things weird here. First, you have a bunch of unnecessary parentheses. (root) is the same thing as root. Second, you're passing root by non-const reference, even though you don't intend to modify it. Third, very minor nit, you're using C-style NULL instead of nullptr. Fourth, why do you print a space before the newline? Fixed up:

void inorder(const Node *root)

{

    if (root != nullptr) {

        inorder(root->left); 

        printf("%dn", root->data); 

        inorder(root->right); 

    } 

}

Remember to remove the redundant parentheses in places like insert(((node)->right),value). It's much easier to read as insert(node->right, value).