Binary Search Tree Visualizer: Step-by-Step Animation & Complexity

Binary Search Tree

Category: Tree / Graph | Time: O(log n) Avg | Space: O(h) Avg

Input Data

Visualization

Visual representation of the data structure

Enter tree data to start visualization.

About Binary Search Tree

A node-based binary tree data structure which has the following properties: the left subtree of a node contains only nodes with keys lesser than the node's key; the right subtree of a node contains only nodes with keys greater than the node's key; the left and right subtree each must also be a binary search tree.

Code Editor

The code is for reference. Editing it won't affect the visualization.

function buildBST(keys) {
  let root = null;
  keys.forEach(key => {
    root = insert(root, key);
  });
  return root;
}

function insert(node, key) {
  if (node === null) {
    return new Node(key);
  }
  if (key < node.key) {
    node.left = insert(node.left, key);
  } else if (key > node.key) {
    node.right = insert(node.right, key);
  }
  return node;
}

Variable State

{
  "status": "Building BST from input array"
}

Binary Search Tree: How It Works

Last updated October 28, 2026

Overview

A binary search tree (BST) keeps the rule 'left subtree < node < right subtree' at every node. That rule lets you search like binary search: compare with the current node and go left or right, discarding a whole subtree each time.

Inserting follows the same path a search would take and attaches the new value as a leaf where the search falls off the tree. The shape of the tree therefore depends entirely on the order of insertions. Random orders give a height of about log n; sorted orders give a single long chain.

The default input 8, 3, 10, 1, 6, 14, 4, 7, 13 builds the textbook example tree: 8 at the root, 3 and 10 below it, then 1, 6 and 14, and finally 4, 7 and 13. Reading it in-order gives 1, 3, 4, 6, 7, 8, 10, 13, 14.

Step by step

To insert, start at the root. If the tree is empty, the new value becomes the root.
If the value is smaller than the current node, go left; otherwise go right.
When the chosen child is null, attach the new node there.
To search, follow the same comparisons and stop when you find the value or reach null.

Complexity

Case	Cost	Why
Search / insert (average)	O(log n)	Random insertion order keeps the height logarithmic.
Search / insert (worst)	O(n)	Sorted insertions create a chain of height n.
In-order traversal	O(n)	Produces the keys in sorted order.
Space	O(n)	One node per key.

When to use it

Ordered sets and maps where you need sorted iteration, range queries, or floor/ceiling lookups.
As the foundation for self-balancing trees (AVL, red-black) used by TreeMap and std::map.
Interview problems on validation, lowest common ancestor, and k-th smallest element.

Common mistakes

Inserting already-sorted data degrades it to a linked list; use a balanced tree when order is not random.
Validating a BST by checking only each node against its direct children misses violations deeper down; pass min/max bounds instead.
Decide how to handle duplicates (reject, count, or always go right) before you write the code.

Worked Example: Binary Search Tree Dry Run

Generated from the same trace that drives the visualizer above, using the default input.

A dry run is the best way to check your understanding of Binary Search Tree: follow each row, predict the next one, and compare. The run below takes 63 steps in total. The Line column refers to the line numbers in the code listing above.

Input: 8,3,10,1,6,14,4,7,13
Result: status = BST construction complete

Step	Line	What happens
1	1	status = Building BST from input array
2	6	status = Inserting 8
3	7	status = Tree is empty, inserting as root
4	8	status = Inserted 8 as root
5	6	status = Inserting 3
6	10	current_node = 8, insert_key = 3, condition = 3 < 8
7	11	current_node = 8, insert_key = 3, status = Going left
8	12	parent = 8, status = Inserting 3 as left child
9	13	status = Inserted 3
10	6	status = Inserting 10
11	10	current_node = 8, insert_key = 10, condition = 10 < 8
12	14	current_node = 8, insert_key = 10, condition = 10 > 8
13	15	parent = 8, status = Inserting 10 as right child
14	16	status = Inserted 10
15	6	status = Inserting 1
16	10	current_node = 8, insert_key = 1, condition = 1 < 8
17	11	current_node = 8, insert_key = 1, status = Going left
18	10	current_node = 3, insert_key = 1, condition = 1 < 3
19	11	current_node = 3, insert_key = 1, status = Going left
20	12	parent = 3, status = Inserting 1 as left child
21	13	status = Inserted 1
22	6	status = Inserting 6
23	10	current_node = 8, insert_key = 6, condition = 6 < 8
24	11	current_node = 8, insert_key = 6, status = Going left
25	10	current_node = 3, insert_key = 6, condition = 6 < 3
26	14	current_node = 3, insert_key = 6, condition = 6 > 3
27	15	parent = 3, status = Inserting 6 as right child
28	16	status = Inserted 6
29	6	status = Inserting 14
30	10	current_node = 8, insert_key = 14, condition = 14 < 8
31	14	current_node = 8, insert_key = 14, condition = 14 > 8
32	10	current_node = 10, insert_key = 14, condition = 14 < 10
33	14	current_node = 10, insert_key = 14, condition = 14 > 10
34	15	parent = 10, status = Inserting 14 as right child
35	16	status = Inserted 14
36	6	status = Inserting 4
37	10	current_node = 8, insert_key = 4, condition = 4 < 8
38	11	current_node = 8, insert_key = 4, status = Going left
39	10	current_node = 3, insert_key = 4, condition = 4 < 3
40	14	current_node = 3, insert_key = 4, condition = 4 > 3

The remaining 23 key steps follow the same pattern. Press play in the visualizer to watch every step through to the result.

Frequently Asked Questions

About Binary Search Tree (BST)

What is a Binary Search Tree (BST)?

A Binary Search Tree is a node-based binary tree data structure which has the following properties: The left subtree of a node contains only nodes with keys lesser than the node's key. The right subtree of a node contains only nodes with keys greater than the node's key. Both the left and right subtrees must also be a binary search tree.

What is the time complexity for search, insert, and delete in a BST?

For a balanced BST, the time complexity for search, insert, and delete operations is O(log n) on average. In the worst-case scenario (an unbalanced tree resembling a linked list), the complexity becomes O(n).

What causes a BST to become unbalanced?

A BST becomes unbalanced if the input data is inserted in a sorted or nearly sorted order. This leads to a degenerate tree where each node has only one child, effectively turning it into a linked list.

How can you traverse a BST to get elements in sorted order?

An in-order traversal (Left, Root, Right) of a BST will visit the nodes in ascending order of their keys.

What is the difference between a BST and a regular Binary Tree?

A Binary Tree is a tree where each node has at most two children. A BST is a special type of Binary Tree that imposes the specific ordering property on its nodes (left child < root < right child), which allows for efficient searching.

How do you find the minimum and maximum value in a BST?

To find the minimum value, you traverse as far left as possible from the root. The leftmost node is the minimum. To find the maximum value, you traverse as far right as possible; the rightmost node is the maximum.

What is the space complexity of a BST?

The space complexity is O(n) to store the n nodes in the tree. The recursive operations (like search or insert) also take O(h) space on the call stack, where h is the height of the tree (which is O(log n) for a balanced tree and O(n) for an unbalanced one).

How does the deletion of a node with two children work in a BST?

To delete a node with two children, you replace the node's value with its in-order successor (the smallest node in its right subtree) or its in-order predecessor (the largest node in its left subtree). Then, you recursively delete the successor/predecessor node, which will have at most one child.

Are BSTs stable for sorting?

If you build a BST and then perform an in-order traversal, the sorting is not stable. The tree structure does not inherently preserve the original order of equal elements.

What are self-balancing BSTs?

Self-balancing BSTs, such as AVL trees or Red-Black trees, are special types of BSTs that automatically perform rotations to keep their height as close to O(log n) as possible, thus guaranteeing O(log n) performance for all operations.

Where can I learn more?

You can find a more detailed explanation on GeeksforGeeks.