DSA — Non-Linear DS

AVL Tree

— min read
O(log n)All Ops
≤1Balance Factor
LeftRotation
RightRotation
✓Self-Balancing
// AVL TREE
Interactive visualization
How It Works
Python Code
Complexity
Quiz
Practice
01
Balance Factor
BF = height(left) - height(right). Valid: -1, 0, +1.
bf = h(left) - h(right)
02
Left Rotation
Right-heavy subtree: rotate left.
Right-Right case
03
Right Rotation
Left-heavy subtree: rotate right.
Left-Left case
04
LR / RL Rotations
Double rotations for Left-Right and Right-Left cases.
python 
def get_height(node):
    if not node: return 0
    return 1 + max(get_height(node.left), get_height(node.right))

def balance_factor(node):
    return get_height(node.left) - get_height(node.right)

def rotate_right(y):
    x = y.left; T2 = x.right
    x.right = y; y.left = T2
    return x
O(log n)
Always
Balanced by construction — no skew possible
O(1)
Rotation
Single or double rotation to rebalance
+1 ptr
Overhead
Height stored per node
Strict
Balance
Tighter than Red-Black tree
An AVL tree's balance factor at any node must be:
Progress 0 / 3 solved
3 problems · 2 PBC · 1 Startup
#072 Validate Binary Search Tree Google, Meta PBC →
#073 Lowest Common Ancestor Apple PBC →
#086 Zigzag Level Order Traversal Zepto STARTUP →
← Binary Search Tree