CC150 4.1 and binary search tree

4_1.cpp

/* CC150 4.1
 * Implement a function to check if a binary tree is balanced.
 * For the purposes of this question, a balanced tree is defined to be a tree such that the heights of the two
 * subtrees of any node never differ by more than one.
 */

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

using namespace std;

int checkHeight(Node *root) // returns the real height if the node is balanced, -1 if unbalanced
{
	if (root == nullptr)
		return 0;
	int leftHeight = checkHeight(root->left);
	if (leftHeight == -1) // the current node is unbalanced if its left child is unbalanced
		return -1;
	int rightHeight = checkHeight(root->right);
	if (rightHeight == -1)
		return -1; // the current node is unbalanced if its right child is unbalanced
	int heightDiff = abs(leftHeight - rightHeight);
	if (heightDiff > 1)
		return -1; // the heights of two subtrees of the current node differ more than one
	else
		return leftHeight >= rightHeight ? leftHeight + 1 : rightHeight + 1; // current node is balanced
}

bool isBalanced(Node *root)
{
	if (checkHeight(root) == -1)
		return false;
	else
		return true;
}

int main()
{
	bstree test;
	int key;
	while (cin >> key)
		test.insert(key);
	cout << isBalanced(test.getRoot()) << endl;
	return 0;
}