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

Question

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

Answer 1

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

Answer 2

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

Answer 3

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