By Pulse


2019-01-08 02:44:14 8 Comments

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; 
}

2 comments

@Deduplicator 2019-01-08 13:52:42

  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.

@Quuxplusone 2019-01-08 15:20:56

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

@Martin York 2019-01-08 19:14:36

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.

@Voo 2019-01-08 19:27:46

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

@Deduplicator 2019-01-08 20:27:00

@Voo Yes, it's a popular extension and C got it earlier with C99.

@Voo 2019-01-08 22:13:04

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

@Quuxplusone 2019-01-08 04:39:45

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

@Pulse 2019-01-08 05:40:29

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.

@Deduplicator 2019-01-08 12:50:53

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.

@Voo 2019-01-08 12:53:15

@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?

@Deduplicator 2019-01-08 12:56:34

@Voo Well, first I would always put the links first. Then, a new Node is created with new Node{nullptr, nullptr, {args...}}, irrespective what {args...} is, even a function-call, and whether the data-type can be copied, moved, or only in-place-constructed.

@Voo 2019-01-08 13:26:56

@Deduplicator Wouldn't that work just as well with a constructor if you use the right signature?

@Deduplicator 2019-01-08 13:57:41

@Voo Then you need a variadic-template forwarding-constructor. A lot of boilerplate for no use, imho, especially as aggregate-initialisation already works. Also, iif you have at least one layer of forwarding the function-call cannot create the return-value directly at the target, though you will probably have that anyway.

@Quuxplusone 2019-01-08 15:14:40

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

@Pulse 2019-01-22 00:15:05

@Quuxplusone Also, why the use of "explicit" before the constructor in the struct?

@Quuxplusone 2019-01-22 00:35:23

@Pulse: The keyword explicit should go on every constructor and conversion operator in your programs, unless you want to enable an implicit conversion (in this case, from int to Node). Implicit conversions are sometimes useful (e.g. from const char * to std::string) but vastly more often are a source of surprising behavior and bugs.

Related Questions

Sponsored Content

1 Answered Questions

1 Answered Questions

[SOLVED] Algorithm that finds two numbers that sum to a target

  • 2018-07-11 13:34:31
  • user3020047
  • 153 View
  • 1 Score
  • 1 Answer
  • Tags:   c# algorithm k-sum

2 Answered Questions

[SOLVED] Generic binary search tree in C++

  • 2018-06-03 21:30:28
  • Incomputable
  • 480 View
  • 7 Score
  • 2 Answer
  • Tags:   c++ tree c++17

1 Answered Questions

[SOLVED] 2D Bin Packing Algorithm Implementation

2 Answered Questions

2 Answered Questions

[SOLVED] Check if a tree is a proper BST

0 Answered Questions

Creating a binary tree from an array

0 Answered Questions

Simple Unbalanced KDTree with 1NN Implementation

  • 2016-08-21 18:38:13
  • Miller
  • 217 View
  • 2 Score
  • 0 Answer
  • Tags:   c++ tree

2 Answered Questions

[SOLVED] Pointer handle - follow-up

1 Answered Questions

[SOLVED] Pointer class/handle

Sponsored Content