ToolSphere

Data Structure Visualizer

Computer science

Visualize BST and AVL trees with named rotations, or binary min and max heaps. Insert, delete, search and compare traversals with step-by-step work.

AVL tree · current result

Height 2 · Size 7

In-order: 10 → 20 → 25 → 28 → 30 → 40 → 50

Height counts edges: a leaf is 0; an empty tree is −1.

Whole numbers −999999 to 999999 · at most 31 nodes. Duplicate keys are ignored.

Current shape

Smaller keys go left; larger keys go right. Scroll the diagram to inspect larger trees.

28201025403050

Traversals

In-order
10 → 20 → 25 → 28 → 30 → 40 → 50
Pre-order
28 → 20 → 10 → 25 → 40 → 30 → 50
Post-order
10 → 25 → 20 → 30 → 50 → 40 → 28
Level order
28 → 20 → 40 → 10 → 25 → 30 → 50

Loaded example · steps

The diagram shows the final structure. Read the trace below for each comparison and change.

  1. Insert 30:
  2. Insert 30 at the empty link.
  3. Insert 20:
  4. Compare 20 with 30.
  5. Go left.
  6. Insert 20 at the empty link.
  7. Insert 10:
  8. Compare 10 with 30.
  9. Go left.
  10. Compare 10 with 20.
  11. Go left.
  12. Insert 10 at the empty link.
  13. LL case at 30: rotate right at 30.
  14. Insert 25:
  15. Compare 25 with 20.
  16. Go right.
  17. Compare 25 with 30.
  18. Go left.
  19. Insert 25 at the empty link.
  20. Insert 28:
  21. Compare 28 with 20.
  22. Go right.
  23. Compare 28 with 30.
  24. Go left.
  25. Compare 28 with 25.
  26. Go right.
  27. Insert 28 at the empty link.
  28. LR case at 30: rotate left at 25, then right at 30.
  29. Insert 40:
  30. Compare 40 with 20.
  31. Go right.
  32. Compare 40 with 28.
  33. Go right.
  34. Compare 40 with 30.
  35. Go right.
  36. Insert 40 at the empty link.
  37. RR case at 20: rotate left at 20.
  38. Insert 50:
  39. Compare 50 with 28.
  40. Go right.
  41. Compare 50 with 30.
  42. Go right.
  43. Compare 50 with 40.
  44. Go right.
  45. Insert 50 at the empty link.
  46. RR case at 30: rotate left at 30.

On this browser only

Give feedback

Did this tool help?

Tell us what worked, what didn’t, or what you’d like next.

Opens Google Forms in a new tab with this tool’s name filled in. No sign-in or email required. Feedback is optional.

How to use Data Structure Visualizer

  1. 1Start with the loaded AVL example, or select a BST, min heap or max heap. Switching structures reloads the example.
  2. 2Enter a whole-number key and choose Insert, Delete or Search. Clear structure starts an empty sequence.
  3. 3Read current height, size and in-order traversal above the controls, then inspect the final tree diagram.
  4. 4Compare traversal orders and read the operation trace for each comparison, rotation or sift.

About Data Structure Visualizer

Trace a BST, AVL tree or binary heap

Use this BST visualizer and AVL tree visualizer to connect a tree drawing with the comparisons that produced it. Start with the loaded example, switch structures or clear the tree and enter your own keys. Each insert, delete or search produces a numbered trace. The diagram shows the final shape, while the trace explains the work. This is practice for a US data structures course, including CS 61B-style material, rather than a university-endorsed homework service.

The result appears before the controls: current height, size and in-order traversal. Height counts edges on the longest root-to-leaf path. A leaf has height zero, and an empty structure has height minus one. Size counts stored nodes. Some instructors count height in nodes instead; check that convention before comparing answers. All operations run in your browser, with no account or software installation required.

Choose the invariant before the operation

A binary search tree stores smaller keys in a node’s left subtree and larger keys in its right subtree. Search follows one branch after each comparison. Inserting keys in a different order can produce a different shape even when the final sorted keys are identical. This tool ignores duplicate BST and AVL keys, treating them as set members rather than storing a frequency or a second node.

An AVL tree adds a balance rule: the heights of the left and right subtrees differ by at most one at every node. After insertion or deletion, the library checks ancestors and rotates unbalanced subtrees. Rotations preserve the search-tree ordering. They change links and the root of a subtree, rather than changing the stored set of keys. The tree is balanced by local height differences, not by requiring every leaf to share a level.

A binary heap serves a different purpose. A min heap keeps each parent no greater than its children; a max heap keeps each parent no smaller. Its shape is complete, filling each level from left to right. Siblings need not be sorted, and a heap’s in-order traversal generally is not sorted. Heaps here allow duplicate values. The displayed array is level order, with indices starting at zero.

Read named AVL rotations

The labels LL, RR, LR and RL describe the heavy path relative to an unbalanced node. An LL case uses a right rotation. An RR case uses a left rotation. LR first rotates the left child left, then the unbalanced node right. RL first rotates the right child right, then the unbalanced node left. The trace names the case and the pivot keys so you can sketch each link change on paper.

Deletion can require rebalancing more than one ancestor. When a heavy child has equal-height subtrees, this implementation chooses the corresponding single rotation. Different valid implementations can therefore produce different balanced shapes after deletion. Compare the ordering and balance invariants as well as the drawing when checking your own implementation.

Worked example from the library

The loaded sequence is 30, 20, 10, 25, 28, 40, 50. In AVL mode, inserting 10 triggers an LL case at 30. Inserting 28 triggers an LR case at 30. Inserting 40 triggers an RR case at 20, and inserting 50 triggers an RR case at 30. The final root is 28, the size is 7 and the height is 2.

The final in-order traversal is 10, 20, 25, 28, 30, 40, 50. Pre-order is 28, 20, 10, 25, 40, 30, 50. Post-order is 10, 25, 20, 30, 50, 40, 28. Level order is 28, 20, 40, 10, 25, 30, 50. These results are computed with the same library as the interactive tool. Search for 25 and follow comparisons from the root to the matching node.

Next delete 20. It has two children, so the tool replaces it with its in-order successor, 25, and removes the original successor node. The remaining in-order traversal is 10, 25, 28, 30, 40, 50. Clearing the structure lets you replay that sequence one insertion at a time, which makes it easier to explain each rotation before reading the trace.

Practice deletion, heaps and traversal orders

BST deletion removes a leaf directly, promotes an only child or uses the smallest key in the right subtree for a two-child node. AVL mode performs the same ordered removal and then repairs balance. Heap insertion appends a value and sifts it up. Heap deletion removes the first matching array position, moves the last value into the gap and repairs heap order upward or downward as needed. Heap search scans the array because the parent rule does not provide BST-style routing.

In-order visits left subtree, node, right subtree. Pre-order visits the node first; post-order visits it last. Level order uses breadth-first visitation. Compare these outputs with your own recursive methods and queue-based traversal. Use the Data Structures Lab for the hash table simulator, or continue to the Algorithms Lab. Inputs are bounded to whole-number keys and a small teaching-sized tree so diagrams remain inspectable; this tool does not benchmark production implementations.

Guides and tutorials

Frequently asked questions

How do I use the BST visualizer?

Choose Binary search tree, then insert whole-number keys one at a time. Search follows ordered comparisons; delete removes the key if present. The final diagram and operation trace update together.

What do LL, RR, LR and RL mean in an AVL tree?

They name the heavy path at an unbalanced node. LL rotates right; RR rotates left; LR rotates the left child left then the node right; RL rotates the right child right then the node left.

How is tree height measured?

Height counts edges on the longest path to a leaf. A leaf has height 0 and an empty tree has height −1. A course using node-count height will give values one greater.

Are duplicate keys allowed?

BST and AVL modes ignore duplicate keys. Min and max heaps keep duplicates. Heap deletion removes one occurrence: the first matching position in the array.

How does deleting a node with two children work?

The BST and AVL modes use the in-order successor, the smallest key in the right subtree. They replace the deleted key and remove the successor from its old location. AVL then repairs balance.

Is a binary heap the same as a binary search tree?

No. A heap is complete and orders parents relative to children. It does not order entire left and right subtrees as a BST does. Heap in-order traversal is generally not sorted.

Which traversals are available?

In-order, pre-order, post-order and level order are shown for the current structure. Level order also matches the displayed heap array.

Does the trace show each comparison?

The numbered trace records comparisons, branch moves, successor selection, rotations and heap sifts. Loading the example shows all its insertions; individual operations replace that trace. The diagram shows the final structure.

What values and sizes are supported?

Use whole numbers from −999999 to 999999 with at most 31 stored nodes. Clear starts an empty structure; loading the example resets it. Invalid operations leave the current structure unchanged.

Can I use this for CS 61B homework?

Use it to check your reasoning in a data structures course. It is independent of any university. Follow your instructor’s conventions for height, duplicate keys, successor versus predecessor deletion and rotation tie-breaking.

Have a suggestion for Data Structure Visualizer?Share your feedback ↗