Skip to content

Instantly share code, notes, and snippets.

@simonayzman
Created November 3, 2016 19:29
Show Gist options
  • Save simonayzman/493e0d08a609aede383d468ba692a4a5 to your computer and use it in GitHub Desktop.
Save simonayzman/493e0d08a609aede383d468ba692a4a5 to your computer and use it in GitHub Desktop.
Determing if a binary tree is balanced
// Note that this is an interesting kind of tree, where there is no overall structure that contains nodes.
// Instead the tree is itself a node.
template<class ItemType>
class Tree {
private:
Tree<ItemType> * left;
Tree<ItemType> * right;
ItemType data;
public:
Tree(ItemType _data){left = NULL; right = NULL; data = _data;}
void insert(ItemType _data){
if ( _data > data){
if (right == NULL){
right = new Tree(_data);
} else{
right->insert(_data);
}
} else{
if (left == NULL){
left = new Tree(_data);
} else{
left->insert(_data);
}
}
}
bool isBalanced(){
if(left == NULL && right == NULL) return true;
if(left == NULL && right != NULL) return right->height() == 0;
if(right == NULL && left != NULL) return left->height() == 0;
return left->isBalanced() && right->isBalanced() && abs(left->height() - right->height()) <= 1;
}
int height(){
if(left == NULL && right == NULL) return 0;
if(left == NULL && right != NULL) return right->height() + 1;
if(right == NULL && left != NULL) return left->height() + 1;
return max(right->height(), left->height()) + 1;
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment