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