My IT Utilities

Binary search tree (BST)

Start from a random binary search tree and insert, search or delete values step by step, with its array form and the C++ code highlighted.

Everything is simulated in this browser; nothing is sent to any server.

No steps

No steps

Binary search tree

Array index

60[0]45[1]85[2]68[5]21[3]55[4]32[8]

Array form

The children of index i are at 2i+1 and 2i+2.

  • Unrelated
  • Already passed
  • Being compared
  • Found
  • New
  • To delete
  • Successor

No steps

Code

#include <iostream>
using namespace std;
class Node { // A node holds its value and pointers to its two children
private: // Private attributes: only the methods touch them
int value;
Node* left;
Node* right;
public:
Node(int v) : value(v), left(nullptr), right(nullptr) {}
int getValue() const { return value; }
Node* getLeft() const { return left; }
Node* getRight() const { return right; }
void setValue(int v) { value = v; }
void setLeft(Node* n) { left = n; }
void setRight(Node* n) { right = n; }
};
Node* insert(Node* root, int v) { // Inserts v into the search tree and returns the root
if (root == nullptr) // Empty spot: the new node goes here
return new Node(v); // Creates the new node
if (v < root->getValue()) // Smaller values go left and larger ones go right
root->setLeft(insert(root->getLeft(), v)); // Goes down the left subtree
else
root->setRight(insert(root->getRight(), v)); // Goes down the right subtree
return root;
}
int main() {
Node* root = buildTree(); // The tree shown, already built
root = insert(root, v); // First call, from main
return 0; // End of the operation
}

This tool starts from a random binary search tree (BST) and lets you change it by hand: type a value from 1 to 99 and press Insert, Search or Delete. Each operation is animated step by step on the tree, with nodes colored by their role: being compared, already passed, new, to delete or successor. Below it you see the same tree as an array, with the children of index i at 2i+1 and 2i+2, and the C++ code highlights the line being run. You can change the size from 3 to 15 nodes, generate another tree and go back to any step. Everything is simulated in your browser.

How to use it

  1. Set the tree size with the slider or press Generate new tree to change the starting point.
  2. Type a value from 1 to 99 and press Insert, Search or Delete; the animation starts on its own.
  3. Move forward or back with the previous and next step buttons, or press Play and change the speed.
  4. Watch the colored nodes, the array form of the tree and the highlighted line of C++ code.

Frequently asked questions

What is a binary search tree and which property does it keep?
It is a binary tree in which every node has at most two children and all the values in the left subtree are smaller than the node's value while all those in the right subtree are larger. Thanks to that property, half of the remaining path can be ruled out at every comparison.
How do insert and search work in a BST and what do they cost?
Both start at the root and compare the value with each node: if it is smaller they go left and if it is larger, right. Search ends when the value is found or nullptr is reached; insert creates the new node in that empty spot. Their cost is proportional to the height of the tree: logarithmic when it is balanced and linear when it is a chain.
What are the three cases of delete and why is the inorder successor used?
If the node is a leaf it is simply removed; if it has one child, that child takes its place; if it has two, the value of the inorder successor, the smallest of the right subtree, is copied into it and the successor's node is deleted. The successor is the next value in order, so it fits in that spot without breaking the BST property, and since it has no left child its deletion is one of the easy cases.
How is a tree stored in an array and why are there gaps?
In heap layout: the root goes at index 0 and the children of index i at 2i+1 and 2i+2. If a node lacks a child, that position stays empty, and the more unbalanced the tree is the more gaps appear, because indexes grow with depth.

Related tools