Balanced BST

A balanced BST is a BST in which the difference in heights of the left and right subtrees is not more than one (1). These example diagrams should make it clear.

Note: Balanced binary tree does not support duplicate keys by default. But if you still want to add duplicates to a balanced binary tree, you can do so by keeping a count of the number of keys in a Node and incrementing it instead of adding a new Node. This is left as side work for you. Post a comment on the discussion if you implemented this!