CC150 4.3

4_3.cpp

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

#include <iostream>

using namespace std;

struct Node {
	int data;
	Node *left, *right;
};

Node *createBST(int *arr, int begin, int end) // end points at one element past the array
{
	if (begin == end)
		return nullptr;
	Node *root = new Node;
	root->data = arr[(begin + end) / 2]; // left subtree is higher if array size is odd
	root->left = createBST(arr, begin, (begin + end) / 2);
	root->right = createBST(arr, (begin + end) / 2 + 1, end);
	return root;
}

void dispInOrder(Node *root) // in-order traversal
{
	if (root == nullptr)
		return;
	dispInOrder(root->left);
	cout << root->data << " ";
	dispInOrder(root->right);
}

void dispPreOrder(Node *root) // pre-order traversal
{
	if (root == nullptr)
		return;
	cout << root->data << " ";
	dispPreOrder(root->left);
	dispPreOrder(root->right);
}

int main()
{
	int N; cin >> N; // input array size
	int *arr = new int[N];
	for (int i = 0; i != N; ++i)
		cin >> arr[i]; // input array data
	Node *root = createBST(arr, 0, N);
	dispInOrder(root);
	cout << endl;
	dispPreOrder(root);
	cout << endl;
	return 0;
}

4_3_simple.cpp

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

#include "bstree.h" // https://gist.github.com/df2d3552fbe8c2342541

using namespace std;

int main()
{
	int N; cin >> N; // input array size
	int *arr = new int[N];
	for (int i = 0; i != N; ++i)
		cin >> arr[i]; // input array data
	bstree tree(arr, N);
	cout << "In-order:   ";
	tree.dispInOrder(tree.getRoot());
	cout << endl;
	cout << "Pre-order:  ";
	tree.dispPreOrder(tree.getRoot());
	cout << endl;
	cout << "Post-order: ";
	tree.dispPostOrder(tree.getRoot());
	cout << endl;
	return 0;
}