7
\$\begingroup\$

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; 
}
\$\endgroup\$
9
\$\begingroup\$

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("%d\n", 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).

\$\endgroup\$
  • \$\begingroup\$ Yeah the unnecessary parentheses came from when I was editing from the previous solution. Also, surprisingly was not aware of putting a constructor / destructor into the struct, thanks for pointing that out to me. Much needed feedback. \$\endgroup\$ – Pulse Jan 8 at 5:40
  • 1
    \$\begingroup\$ Actually, leaving Node without any user-declared ctors and functions is much better: It doesn't have any invariants, as much as anyone might pretend, and they only get in the way of implementing the list efficiently and correctly, which does. \$\endgroup\$ – Deduplicator Jan 8 at 12:50
  • 1
    \$\begingroup\$ @Deduplicator "A node always has the data set" is quite obviously a (very simple) invariant which the constructor nicely enforces. And in what way does it make the implementation harder? \$\endgroup\$ – Voo Jan 8 at 12:53
  • 1
    \$\begingroup\$ @Deduplicator Wouldn't that work just as well with a constructor if you use the right signature? \$\endgroup\$ – Voo Jan 8 at 13:26
  • 1
    \$\begingroup\$ @Deduplicator is wrong: Providing a constructor is obviously correct (especially for this programmer's level of expertise). Besides the "Node's data is always set" invariant, there are at least two more: "Node's left pointer is always initialized (never garbage)" and "Node's right pointer is always initialized (never garbage)." If Node were an internal implementation detail of some larger List type, then making it a POD struct might be a reasonable optimization; but remember that correctness trumps premature optimization. (That said, Deduplicator's answer deserves more upvotes. :)) \$\endgroup\$ – Quuxplusone Jan 8 at 15:14
5
\$\begingroup\$
  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("%d\n", 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.

\$\endgroup\$
  • 1
    \$\begingroup\$ On #3, I think it's worth mentioning that if you use unique_ptr for the links, then the destructor of Node becomes recursive, which means it's probably not a good idea for real code (but is still a good suggestion for OP to think about and understand how it'd work). \$\endgroup\$ – Quuxplusone Jan 8 at 15:20
  • 2
    \$\begingroup\$ The ` extra-whitespace at the end of lines` This is more important than it looks (it feels trivial but I agree with deduplicator that it is important). People specifically set their editors to show extra white space at then end of lines. \$\endgroup\$ – Martin York Jan 8 at 19:14
  • \$\begingroup\$ Relying on the order of members in such an implicit and hidden way for #3 strikes me as an awful, awful maintenance burden for very little benefit. Using the c++20 syntax is fine though (that one's really only in c++20? I guess before it was just a really popular extension?) \$\endgroup\$ – Voo Jan 8 at 19:27
  • \$\begingroup\$ @Voo Yes, it's a popular extension and C got it earlier with C99. \$\endgroup\$ – Deduplicator Jan 8 at 20:27
  • \$\begingroup\$ @Deduplicator Yeah I know that C had it for years, I just assumed C++ would've gotten it around c++11 or possibly 14 as well. Well, better late than never. \$\endgroup\$ – Voo Jan 8 at 22:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.