Search Tree Workshop
About this app
Insert, search and delete numbers in a binary search tree: the comparison path lights up node by node with the sentence from the slides (‘22 > 21: right’). Below, the pointer of a sorted linked list runs along, and two counters compare tree and list. Nodes stand in inorder sequence and only move sideways on insertion. 1 2 3 4 5 makes the tree degenerate into a list (depth 5 instead of 3). Plus the three deletion cases, an object view with node cards and the exercises max, depth and search tree by hand.
How a binary search tree orders values
In a binary search tree all smaller values lie in a node's left subtree and all larger ones in its right subtree. To search or insert, you compare from the root and go left or right depending on the result. In a balanced tree this takes about log₂(n) comparisons. If the values are inserted in sorted order, however, the tree degenerates into a list and searching becomes as slow as in a linked list. An inorder traversal always outputs the values in sorted order.
What the app shows
Nodes are placed side by side by their inorder position and stacked by their depth, so when you insert they only move sideways. The comparison path lights up node by node, with sentences such as “22 > 21: right”. Below, the pointer of a sorted linked list with the same values runs along, and bars compare the number of comparisons. Readouts show the node count, the depth and the best possible depth.
Try it yourself
Insert numbers from 1 to 99 one at a time or as a whole sequence, search and delete them; seven sequences are ready to use. Enter 1 2 3 4 5 and watch the tree degenerate into a list: depth 5 instead of 3. The three deletion cases (leaf, one child, two children) can be played one by one. An object view shows the nodes as cards with arrows, the code panel the running Python code, and exercises on inorder, maximum and depth go deeper.
Frequently asked questions
- What is a binary search tree?
- A binary tree in which, for every node, all values in the left subtree are smaller and all values in the right subtree larger. This lets a search rule out one side at every node, much like binary search in a sorted array.
- Why can a binary search tree degenerate?
- Its shape depends on the insertion order. If the values arrive sorted, such as 1, 2, 3, 4, 5, every new node hangs to the right of the previous one. The tree becomes a chain of depth n and searching costs O(n) instead of O(log n). Self-balancing trees such as AVL or red-black trees prevent this.
- How do you delete a node from a binary search tree?
- A leaf is simply removed. If the node has one child, that child takes its place. If it has two children, its value is replaced by the next larger value (the minimum of the right subtree), which is then deleted there.
- What can I try in the search tree workshop?
- Inserting, searching and deleting with a glowing comparison path, a comparison with a sorted list, degenerate trees, the three deletion cases, an object view with node cards and exercises on inorder, maximum and depth.
Subject: Computer science
More from Computer science
- Ackermann function
- Elevator simulator
- Binary workshop
- Binary versus linear search
- The Collatz problem
- Inside a CPU
- Swap the inside
- One frame in 16 milliseconds — how a game engine renders an image (3D)
A VisuApp by heyprof: interactive, free in your browser, no sign-up. What is a VisuApp? · All apps