binarySearchTree.cpp

/*
Contents of this file were provided on Moodle, except:
- findMinimum(BinTreeNode *tree)

Modified source code to use 'nullptr'
*/

#include <iostream>

class BinTreeNode {
public:
	int value;
	BinTreeNode* left;
	BinTreeNode* right;

	BinTreeNode(int value) {
		this->value = value;
		this->left = nullptr;
		this->right = nullptr;
	}

};

BinTreeNode* tree_insert(BinTreeNode* tree, int item) {
	if (tree == nullptr)
		tree = new BinTreeNode(item);
	else
		if (item < tree->value)
			if (tree->left == nullptr)
				tree->left = new BinTreeNode(item);
			else
				tree_insert(tree->left, item);
		else
			if (tree->right == nullptr)
				tree->right = new BinTreeNode(item);
			else
				tree_insert(tree->right, item);
	return tree;

}

void postorder(BinTreeNode* tree) {
	if (tree->left != nullptr)
		postorder(tree->left);
	if (tree->right != nullptr)
		postorder(tree->right);
	std::cout << tree->value << std::endl;

}

void in_order(BinTreeNode* tree) {
	if (tree->left != nullptr)
		in_order(tree->left);
	std::cout << tree->value << std::endl;
	if (tree->right != nullptr)
		in_order(tree->right);
}
// method to return the smallest value in the BST
int findMinimum(BinTreeNode *tree) {
	// return value of current element if it doesn't have a child on the left
	// (so if it is the smallest element)
	if (tree->left == nullptr) {
		return tree->value;
	}
	// call the method recursively on the left child otherwise
	return findMinimum(tree->left);
}

int main(int argc, char *argv[]) {
	BinTreeNode* t = tree_insert(0, 6);
	tree_insert(t, 3);
	tree_insert(t, 4);
	tree_insert(t, 2);
	tree_insert(t, 5);
	tree_insert(t, 10);
	tree_insert(t, 11);
	in_order(t);
	std::cout << "Minimum: " << findMinimum(t) << std::endl;
	return 0;
}