Building a minimal-height BST from a monotonically increasingly ordered array structure

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 
#include 
#include 

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

template 
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 
void create_bst_helper(std::unique_ptr& root, It start, It end) {
    if(start >= end) {
        return;
    }

    if(!root) {
        It midpoint = get_midpoint_iterator(start, end);
        root = std::move(std::unique_ptr(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 
std::unique_ptr create_bst(It start, It end) {
    std::unique_ptr bst = nullptr;
    if(start != end) {
        create_bst_helper(bst, start, end);
    }
    return bst;
}

int main() {
    std::vector v{1,2,3,4,5,6};
    std::unique_ptr bst = create_bst(std::begin(v), std::end(v));
}

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 
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 
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(new Node(*midpoint)));

This can be more clearly expressed with:

root = std::make_unique(*midpoint);

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

std::unique_ptr bst = nullptr;

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

std::unique_ptr bst; // equivalent to `= nullptr;`

StackExchange Code Review Q#142421, answer score: 5