8
\$\begingroup\$

Problem statement:

Given a sorted (increasing order) array with unique integer elements, write an algorithm to create a binary search tree with minimal height.

Assumptions:

The array (and therefore BST) will only contain the type int. Other integral types are unsupported.

The problem statement's description is a precondition and can therefore be taken for granted. No checks of uniqueness and unsortedness will be needed.

The algorithm:

Divide and conquer. The midpoint of the array will be the root. Because BSTs are a recursive data structure, the left and right pointers of the root are also BSTs. Recurse on the (beginning, midpoint-1) and the (midpoint+1, end) of the array.

Any recommendations, tips, and corrections are welcome!

#include <iostream>
#include <vector>
#include <memory>

struct Node {
    int data;
    std::unique_ptr<Node> left;
    std::unique_ptr<Node> right;
    Node() : left(), right() {}
    Node(int data) : data(data), left(), right() {}
};

template <typename It>
It get_midpoint_iterator(It start, It end) {
    auto midpoint = std::distance(start, end) / 2;
    It mid = start;
    std::advance(mid, midpoint);
    return mid;
}

template <typename It>
void create_bst_helper(std::unique_ptr<Node>& root, It start, It end) {
    if(start >= end) {
        return;
    }

    if(!root) {
        It midpoint = get_midpoint_iterator(start, end);
        root = std::move(std::unique_ptr<Node>(new Node(*midpoint)));
        // left subtree is [start, midpoint) 
        create_bst_helper(root->left, start, midpoint);
        // right subtree is [midpoint+1, end)
        create_bst_helper(root->right, std::next(midpoint, 1), end);
    }
}

template <typename It>
std::unique_ptr<Node> create_bst(It start, It end) {
    std::unique_ptr<Node> bst = nullptr;
    if(start != end) {
        create_bst_helper(bst, start, end);
    }
    return bst;
}

int main() {
    std::vector<int> v{1,2,3,4,5,6};
    std::unique_ptr<Node> bst = create_bst(std::begin(v), std::end(v));
}
\$\endgroup\$
  • \$\begingroup\$ Let us continue this discussion in chat. \$\endgroup\$ – Incomputable Sep 25 '16 at 18:11
  • \$\begingroup\$ I would like to add that unique_ptr<> may cause stackoverflow, indirectly, if the tree is too deep. It was presented in Herb Sutter's talk. Very funny though. \$\endgroup\$ – Incomputable Sep 26 '16 at 15:39
  • \$\begingroup\$ This is already a binary search tree. Just because it isn't in a fancy tree data structure doesn't mean it can't be used as a binary search tree. \$\endgroup\$ – noob Sep 29 '16 at 22:59
5
\$\begingroup\$

Simplified Node type

This constructor:

Node() : left(), right() {}

Can be replaced with:

constexpr Node() noexcept
    : data{}
{}

The default constructor of std::unique_ptr<> will initialize its contained pointer to nullptr, so you do not need to explicitly call it.

All of your classes' data members have non-throwing default constructors. Thus, you can safely mark yours as noexcept.

We can mark this constructor as constexpr, because similarly, all of your data member's default constructors are constexpr. This can be useful if you want to define a static compile-time special value, such as the empty node value.


This constructor:

Node(int data) : data(data), left(), right() {}

Can be replaced with:

constexpr Node(int const data) noexcept
    : data(data)
{}
  • We mark the parameter as const, because it is not modified.
  • We remove the redundant calls to the default constructors of left and right.
  • We mark it as constexpr and noexcept.
  • We use new lines for readability.

Finally, since you can live with initializing data with zero, you can replace both constructors with a single one:

constexpr Node(int const data = 0) noexcept
//                          ^^^^^ default value
    : data(data)
{}

Simplified calls

Your get_midpoint_iterator() function can be simplified. Here is how it currently looks:

template <typename It>
It get_midpoint_iterator(It start, It end) {
    auto midpoint = std::distance(start, end) / 2;
    It mid = start;
    std::advance(mid, midpoint);
    return mid;
}

These statements:

It mid = start;
std::advance(mid, midpoint);
return mid;

Can be replaced with:

return std::next(mid, midpoint);

View the documentation here: http://en.cppreference.com/w/cpp/iterator/next


Since your function's body now looks like this:

auto midpoint = std::distance(start, end) / 2;
return std::next(start, midpoint);

You can simply erase midpoint and put the calculation at the function call location:

return std::next(start, std::distance(start, end) / 2);

You end up with a concise function that is guaranteed copy elision in C++17.

template <typename It>
It get_midpoint_iterator(It start, It end) {
    return std::next(start, std::distance(start, end) / 2);
}

As @miscco points out, this obfuscates the operation slightly, so you might also want to add a comment indicating that std::distance(start, end) / 2 is the midpoint.


Your create_bst_helper() function currently initializes a std::unique_ptr<> in the following fashion:

root = std::move(std::unique_ptr<Node>(new Node(*midpoint)));

This can be more clearly expressed with:

root = std::make_unique<Node>(*midpoint);

Your create_bst_helper() function currently creates a std::unique_ptr<> instance by assigning nullptr to it:

std::unique_ptr<Node> bst = nullptr;

The default constructor of std::unique_ptr<> already does so:

std::unique_ptr<Node> bst; // equivalent to `= nullptr;`
\$\endgroup\$
  • \$\begingroup\$ I had the same comment about get_midpoint_iterator, however I would suggest to not cramp it together into a one liner. With auto midpoint = std::distance(start, end) / 2; it is way more descriptive and the compiler will optimize it way anyway \$\endgroup\$ – miscco Sep 26 '16 at 7:31
  • \$\begingroup\$ I've seen noexcept a lot. Does it promise any performance boosts (through compiler guarantees), or is it mostly documentation for maintainers? \$\endgroup\$ – erip Sep 26 '16 at 13:05
  • \$\begingroup\$ It is mostly for maintainers and users (you don't want to surround every call with a try-catch block. There are some performance benefits as well: Reduced code size helps the cache in larger programs and there are many standard library tools that are more efficient if your type is noexcept-move-constructible, for example. \$\endgroup\$ – user2296177 Sep 26 '16 at 15:10
  • \$\begingroup\$ @miscco We can gain both advantages by just having a small comment above the return line that indicates midpoint = std::distance(start, end) / 2. \$\endgroup\$ – user2296177 Sep 26 '16 at 15:16
3
\$\begingroup\$

It looks ok except for one major bug.

  1. You do not include all necessary headers std::advance is in #include <iterator>

  2. I would utilize std::next in your midpoint calculation, as it does not modify the original iterator. So the code would simplify to:

    template <typename It>
    It get_midpoint_iterator(It start, It end) {
        auto midpoint = std::distance(start, end) / 2;
        return std::next(start, midpoint);
    }
    
  3. Your bst_create_helper is buggy, as it doesnt do anything if root is not the nullptr. Maybe you just misplaced the curly brace?

    template <typename It>
    void create_bst_helper(std::unique_ptr<Node>& root, It start, It end) {
        if(start >= end) {
            return;
        }
    
        It midpoint = get_midpoint_iterator(start, end);
        if(!root) {
            root = std::move(std::unique_ptr<Node>(new Node(*midpoint)));
        }
        // left subtree is [start, midpoint) 
        create_bst_helper(root->left, start, midpoint);
        // right subtree is [midpoint+1, end)
        create_bst_helper(root->right, std::next(midpoint, 1), end);        
    }
    
\$\endgroup\$
  • \$\begingroup\$ I think that left and right are always nullptr, by design (in the node constructor, call to left() and right() makes them nullptr). \$\endgroup\$ – Incomputable Sep 25 '16 at 18:52
  • \$\begingroup\$ If that is the case, then the check seems superfluous \$\endgroup\$ – miscco Sep 25 '16 at 19:29
  • \$\begingroup\$ @misco, agreed. I think that he wanted to be safe, though nothing will tell him if something goes wrong. \$\endgroup\$ – Incomputable Sep 25 '16 at 19:30
  • \$\begingroup\$ @miscco Yes, it seems my check is superfluous. :) root should always be nullptr as a precondition. \$\endgroup\$ – erip Sep 26 '16 at 11:13
  • \$\begingroup\$ Also, it's very curious how my code compiled without <iterator>... \$\endgroup\$ – erip Sep 26 '16 at 11:17
3
\$\begingroup\$

My issues are very minor.

Uneeded Constructor

Don't see why you have a default constructor here?

struct Node {
    int data;
    std::unique_ptr<Node> left;
    std::unique_ptr<Node> right;
    Node() : left(), right() {}         // Does not seem to be used.
                                        // Also it leaves data uninitialized
                                        // thus seems dangerious and invites
                                        // accidental UB.
                                        // Note: Reading an uninitialized
                                        //       value is UB.
    Node(int data) : data(data), left(), right() {}
};

Assignment of unique_ptr

root = std::move(std::unique_ptr<Node>(new Node(*midpoint)));

The creation of the unique_ptr here already creates an pr-value you do not need to call std::move() to convert it to a pr-value for assignment.

// This should work.
root = std::unique_ptr<Node>(new Node(*midpoint));

Since C++14 (so all the modern compiler support it) std::make_unique() is supported as a shorthand for this:

root = std::make_unique<Node>(*midpoint);

Order Of Creation

Personally I would not create the node until I had successfully completed the two sub-trees. Less objects to release if something goes wrong.

std::unique_ptr<Node> left  = create_bst(start, midpoint);
std::unique_ptr<Node> right = create_bst(std::next(midpoint, 1), end);
return make_unique<Node>(*midpoint, std::move(left), std::move(right));

But honestly its like 6 of one half a dozen of the other so I would not bother changing your code it's absolutely fine.

Iterator Comparison

if(start >= end) {
    return;
}

Your function works for Random Access/Bi-Directional/Forward Iterators. In every regard apart from the above.

This will only work for Random Access iterators. So you seem to be needlessly limiting yourself to random accesses iterators when all the above are supported by the use of:

if(start == end) {
    return;
}
\$\endgroup\$
  • \$\begingroup\$ If I were to go with route you describe in Order of Creation, presumably I would need to define a ctor Node(int data, std::unique_ptr<Node>&& left, std::unique_ptr<Node>&& right), yes? \$\endgroup\$ – erip Sep 26 '16 at 1:06
  • \$\begingroup\$ (Uneed a bold n that's not afraid of dangerious UB.) \$\endgroup\$ – greybeard Sep 26 '16 at 5:54
  • \$\begingroup\$ @erip: Yes you would need to change the constructor as you describe. \$\endgroup\$ – Martin York Sep 26 '16 at 6:52

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.