Created
November 3, 2016 19:29
-
-
Save simonayzman/493e0d08a609aede383d468ba692a4a5 to your computer and use it in GitHub Desktop.
Determing if a binary tree is balanced
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
// 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