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.