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 inO(log n)
time.