Interview frequency: …
Short answer
A BST ensures the left child is smaller than a node and the right child is larger. However, inserting sorted values turns it into a skewed line with O(N) operations, so self-balancing trees use rotations to maintain O(log N) depth.
Explanation
AVL trees enforce strict balance: the height difference between any two subtrees is at most one, making them ideal for frequent fast lookups. Red-Black trees use looser balance based on red/black node-coloring rules, reducing the number of rotations needed during insertion and deletion. They are therefore used as a default structure in major language libraries, such as Java's TreeMap and C++'s std::map.
Code example
class Node:
def __init__(self, key):
self.key, self.left, self.right = key, None, None
def insert(root, key):
if root is None:
return Node(key)
if key < root.key:
root.left = insert(root.left, key)
else:
root.right = insert(root.right, key)
return root
def height(node):
return 0 if node is None else 1 + max(height(node.left), height(node.right))
degenerate = None
for k in range(1, 8): # sorted input
degenerate = insert(degenerate, k)
print(height(degenerate)) # 7 → behaves like a linked list, O(n)
balanced = None
for k in [4, 2, 6, 1, 3, 5, 7]:
balanced = insert(balanced, k)
print(height(balanced)) # 3 → O(log n); AVL/Red-Black keep this via rotationsCommon mistakes
- Believing that a BST always guarantees O(log N) without self-balancing mechanisms.