min_bst.cpp

#include <iostream>
#include <vector>
#include <stack>
#include <utility>

using namespace std;

struct Node {
	int val = -1;
	Node* left = 0;
	Node* right = 0;
};

Node* rBuildMinTree(const vector<int>& a, int start = 0, int end = -1) {
	if (end == -1) { end = a.size(); }
	if (start >= end) { return 0; }
	int m = start + (end - start) / 2;
	return new Node{a[m], rBuildMinTree(a, start, m),
					   rBuildMinTree(a, m + 1, end)};
}

int getMid(int s, int e) {
	return s + (e - s) / 2;
}

Node* buildMinTree(const vector<int>& a) {
	int s = 0, e = a.size();
	if (s == e) { return 0; }
	int m = getMid(s, e);
	stack<Node*> nodeStack;
	stack<pair<int, int>> boundsStack;
	Node* root = new Node{a[m]};
	nodeStack.push(root);
	boundsStack.push(make_pair(s, e));
	while (!nodeStack.empty()) {
		Node* n = nodeStack.top(); 
		nodeStack.pop();
		s = boundsStack.top().first;
		e = boundsStack.top().second;
		boundsStack.pop();
		int m = getMid(s, e);
		if (s < m) {
			int ml = getMid(s, m);
			n->left = new Node{a[ml]};
			nodeStack.push(n->left);
			boundsStack.push(make_pair(s, m));
		}
		if ( m + 1 < e) {
			int mr = getMid(m + 1, e);
			n->right = new Node{a[mr]};
			nodeStack.push(n->right);
			boundsStack.push(make_pair(m + 1, e));
		}
	}
	return root;
}


void printTreeInOrder(Node* n) {
	if (!n) { return; }
	printTreeInOrder(n->left);
	cout << n->val << ' ';
	printTreeInOrder(n->right);
}

int main() {

	Node* root1 = buildMinTree({1,2,3,4,5,6});
	Node* root2 = buildMinTree({0});
	Node* root3 = buildMinTree({0,1});
	Node* root4 = buildMinTree({0,1,2});

	printTreeInOrder(root1);
	cout << endl;
	printTreeInOrder(root2);
	cout << endl;
	printTreeInOrder(root3);
	cout << endl;
	printTreeInOrder(root4);
	cout << endl;

	return 0;
}

Objective: Write a function that takes a sorted array and turns it into a BST of min height.