What is Balanced Tree and why is that important?

A tree is said to be balanced only when all three conditions satisfy:

• The left and right subtrees height differ by at most one
• The left subtree is balanced
• The right subtree is balanced

Height-balancing requirement:

• A node in a tree is height-balanced if the heights of its subtrees differ by no more than 1.
• A tree is height-balanced if all of its nodes are height-balanced.

In a balanced BST, the height of the tree is log n where n is the number of elements in the tree. In the worst case and in an unbalanced BST, the height of the tree can be upto n which makes it same as a linked list. In the worst case each of the operations (lookup, insertion and deletion) takes time O(n) that shall be avoided.

Balanced BST maintains h = O(log n) so all operations run in O(log n) time.