AVL Tree (Balanced BST)

DSA · Trees

Theory

An AVL tree is a self-balancing BST in which the heights of each node's left and right subtrees differ by at most one. After every insert or delete it checks the balance factor and fixes violations with rotations: a single left or right rotation, or a double rotation (left-right or right-left). This guarantees a height of O(log n), so search, insert and delete are always O(log n).

Why we use it

Balancing prevents the O(n) worst case of a plain BST when data arrives in sorted order.

When to use it

Use self-balancing trees when you need guaranteed O(log n) operations on ordered data; in practice you use library versions (red-black trees, B-trees) rather than writing your own.

How it works

  1. Insert like a BST
  2. Update heights on the way up
  3. |height(left) - height(right)| > 1? Yes: Rotate (LL, RR, LR, RL). No: Continue up.
  4. Tree stays balanced: O(log n)

Syntax

balance = height(left) - height(right)
balance > 1  and new key < left.val   -> right rotate
balance < -1 and new key > right.val  -> left rotate
LR / RL cases -> double rotation

All operations: O(log n)

Example

class Node:
    def __init__(self, val):
        self.val, self.left, self.right, self.h = val, None, None, 1

def h(n): return n.h if n else 0
def fix(n): n.h = 1 + max(h(n.left), h(n.right))

def rotate_right(y):
    x = y.left; y.left = x.right; x.right = y
    fix(y); fix(x); return x

def rotate_left(x):
    y = x.right; x.right = y.left; y.left = x
    fix(x); fix(y); return y

def insert(n, val):
    if not n: return Node(val)
    if val < n.val: n.left = insert(n.left, val)
    else: n.right = insert(n.right, val)
    fix(n)
    bal = h(n.left) - h(n.right)
    if bal > 1 and val < n.left.val: return rotate_right(n)
    if bal < -1 and val > n.right.val: return rotate_left(n)
    if bal > 1: n.left = rotate_left(n.left); return rotate_right(n)
    if bal < -1: n.right = rotate_right(n.right); return rotate_left(n)
    return n

root = None
for v in range(1, 8):          # sorted input would make a plain BST a chain
    root = insert(root, v)
print("Root:", root.val, "| Height:", root.h, "(a plain BST would have height 7)")

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic