Data Structure 📂 Tree in Data Structure · 4 of 7 19 min read Updated Jun 01, 2026

Tree Visualiser Game — Binary Search Tree, AVL & Red-Black, Step by Step

An interactive tree game: enter up to 15 numbers, choose Binary Search Tree, AVL, or Red-Black, and watch each value insert step by step — comparing down, attaching the new node, then rebalancing with rotations (AVL & Red-Black) and recolouring (Red-Black). Live stats track comparisons, rotations, recolours, and tree height versus the ideal, making complexity visible. The classic sorted-input trap shows a BST degenerate to a line while AVL and Red-Black stay balanced. No code, theme-aware (light

Tree Lab

Tree Visualiser — BST · AVL · Red-Black

Type up to 15 numbers, choose a tree type, and press Play. Each value is inserted one at a time: watch the search compare its way down, the new node attach, then the tree rebalance with rotations (AVL & Red-Black) and recolouring (Red-Black). The stats track every operation and the tree's height — the key to its complexity.

Numbers Tree

Node Comparing New Rotating Recolour Red Black

Press Play or Step ▶ to build the tree.

0Comparisons

0Rotations

0Recolours

0Height

0 / 0Step

Speed

Guide

How to Play

🎮 Four Steps

Type up to 15 numbers (commas or spaces) and click Apply, or hit Random.

Pick a Tree type: plain Binary Search Tree, self-balancing AVL, or Red-Black.

Press Play, or step one operation at a time with Step ▶ / Back. Adjust Speed to follow along.

Compare the Height and operation counts across the three tree types — that's their complexity made visible.

💡

Try the Sorted-Input Trap

Enter numbers in order (e.g. 10, 20, 30, 40, 50, 60, 70) and run a Binary Search Tree. It degenerates into a straight line (height = n) — search becomes O(n)! Now switch to AVL or Red-Black with the same input and watch rotations keep it short and bushy. That's exactly why self-balancing trees exist.

Reference

How the Three Trees Compare

Tree	Balanced?	Search / Insert	Worst height	Rebalancing cost
Binary Search Tree	No	O(log n) avg, O(n) worst	n (a line)	None
AVL Tree	Strictly	O(log n)	≈ 1.44 log₂n	Rotations (more)
Red-Black Tree	Loosely	O(log n)	≤ 2 log₂(n+1)	Recolours + fewer rotations

🌳

The Takeaway

A plain BST is simplest but can degrade to a linked list. AVL keeps the tightest balance — fastest lookups, but more rotations on insert. Red-Black balances more loosely using cheap recolouring, so it does fewer rotations — which is why it backs many standard libraries (like C++ std::map and Java TreeMap).