Dtyjlui

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).

1. I would have expected an empty line between your includes and the declaration of Node.




2. You seem inordinately fond of having extra-whitespace at the end of lines. Loose it, both in the code and in the output, as it at best irritates co-workers and diff.




3. Consider using smartpointers, specifically std::unique_ptr for the link- and root-pointer. That way, you won't leak your tree. Admittedly, not freeing might be an intentional optimisation for faster shutdown, but that seems unlikely.
   Yes, you have as much recursion as in inorder(), using an explicit stack could avoid that. Or much more iteration. Or having back-pointers. Or a custom area-allocator.




4. As a matter of course, I would always put the links first in any kind of node-class.



5. 
   

   newNode is very expansively written, and if the value_type isn't trivially constructible, might not be optimisable by the compiler from initialisation+assignment for all members to just initialisation. Why ask it to?

   
   
   

   Node* newNode(int value) {
   
       return new Node{value};
   
       // Or if you move the links: `new Node{nullptr, nullptr, value}`
   
       // With C++20: `new Node{.data = value}`
   
   }
   
   

   
   
   

   That can easily be used for non-copyable, non-movable, and even only in-place-constructible types.

   
   



6. Prefer nullptr for nullpointer-constants, if you actually need one. That is more type-safe, and sometimes enables additional optimisations.




7. Try to take advantage of references to simplify calling your functions.




8. insert() drops any duplicate values. Is that intentional? If so, that needs to be called out in a comment, or made more obvious from the code-structure!



9. 
   

   insert() has no need to recurse:

   
   
   

   void insert(Node* &root, int value) {
   
       auto p = &root;
   
       while (*p && p[0]->data != value)
   
           p = p[0]->data > value ? &p[0]->left : &p[0]->right;
   
       if (!*p)
   
           *p = newNode(value);
   
   }
   
   

   
   



10. inorder() only needs to know the root-node, not where the pointer to it is saved. Also, it never modifies anything. Thus, it should accept Node const* or Node const&.




11. inorder() cannot throw by design, so mark it noexcept.




12. Try to minimize the level of indentation. Guards at the start of a function are quite idiomatic.



13. 
    

    What does inorder() do in order? Ah, printing. So, why not call it print_inorder()?

    
    
    

    void print_inorder(const Node *root) noexcept {
    
        if (!root)
    
            return;
    
        print_inorder(root->left);
    
        printf("%dn", root->data);
    
        print_inorder(root->right);
    
    }
    
    

    
    



14. Some would suggest favoring iostreams over stdio for added type-safety, but there are downsides for that too.




15. return 0; is implicit for main().




16. Naturally, for any further use you would want to wrap your data-structure in its own class-template with members for observing, modifying, iterating, and ctors / dtor for enforcing the invariants and manage the resources. But ensuring full re-usability is probably far out-of-scope at the moment.