Last active
August 29, 2015 14:03
-
-
Save ivycheung1208/e448a924ba7d3b4d0f8b to your computer and use it in GitHub Desktop.
CC150 4.1 and binary search tree
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* 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; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment