Binary search tree insertion, search and deletion: Examples & Code

Algorithm Visualizations November 16, 2026 javascript

Published by Dimitris Kougioumtzis · Updated

Build an unbalanced search tree, insert a key, search for a key, then delete a key using the inorder successor when necessary. Duplicate keys are ignored.

Maintain smaller keys in the left subtree and larger keys in the right subtree. Search follows one branch at each comparison. Deletion reconnects a sole child, or copies the inorder successor before removing that successor.

Open the 3D visualization

Binary search tree insertion, search and deletion example state preview
Preview of the example's final state. Complete values are available in the worked example and interactive timeline.

When to use Binary search tree insertion, search and deletion

Teaching ordered-set operations and the structural cases in binary search tree deletion.

Choosing an alternative

AVL and red-black trees enforce balance for logarithmic worst-case operations; an ordinary BST can become a chain under sorted insertion.

Worked example: input and state changes

Example input

8,3,10,1,6,14 | 4,6,3

These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.

  1. Step 0: Insert initial key 8; equal keys share one node.

    State at this checkpoint
    {
      "values": [
        8
      ],
      "active": [
        0
      ],
      "kind": "graph",
      "tree": true,
      "chosen": [],
      "visited": []
    }
  2. Step 4: Insert initial key 6; equal keys share one node.

    State at this checkpoint
    {
      "values": [
        8,
        3,
        10,
        1,
        6
      ],
      "active": [
        4
      ],
      "kind": "graph",
      "tree": true,
      "chosen": [],
      "visited": []
    }
  3. Step 8: Search 6: compare with 3, then descend right.

    State at this checkpoint
    {
      "values": [
        8,
        3,
        10,
        1,
        6,
        null,
        14,
        null,
        null,
        4
      ],
      "active": [
        1
      ],
      "kind": "graph",
      "tree": true,
      "chosen": [],
      "visited": []
    }
  4. Step 11: Delete 3: inspect 3.

    State at this checkpoint
    {
      "values": [
        8,
        3,
        10,
        1,
        6,
        null,
        14,
        null,
        null,
        4
      ],
      "active": [
        1
      ],
      "kind": "graph",
      "tree": true,
      "chosen": [],
      "visited": []
    }
  5. Step 15: Delete 3 complete. Inorder keys: 1, 4, 6, 8, 10, 14. Search result before deletion: 1.

    State at this checkpoint
    {
      "values": [
        8,
        4,
        10,
        1,
        6,
        null,
        14
      ],
      "active": [],
      "kind": "graph",
      "tree": true,
      "chosen": [],
      "visited": [],
      "result": 1,
      "ordered": [
        1,
        4,
        6,
        8,
        10,
        14
      ]
    }

Expected final state

Delete 3 complete. Inorder keys: 1, 4, 6, 8, 10, 14. Search result before deletion: 1.

Complexity and input bounds

Family: Trees. Time complexity: O(h) per operation.

Implementation detail: The UI accepts one to six initial keys and one insert/search/delete sequence. Downloads also accept an empty initial tree, return the search result before deletion, and write the remaining count followed by inorder keys. Operations cost O(h), worst-case O(n); building the whole unbalanced tree can cost O(n^2).

Space complexity: O(n) auxiliary storage for node arrays and traversal stack in the portable version, or nodes and recursion in Python. Saved frames use additional space.

Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.

1..6 initial integer keys | insert,search,delete keys. Keys 0..99; duplicates ignored.

The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.

Common mistakes and limitations

Duplicates are ignored. Deleting the root may change the root pointer. A two-child deletion must preserve the successor’s right subtree. The displayed search occurs after insertion and before deletion.

Further reading

For background on algorithm analysis and the JavaScript function interface:

Editorial and testing approach · Browse all algorithm guides

Complete JavaScript implementation

javascript
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// Unbalanced BST set: n 0..6 initial keys, all keys 0..99. Insert insertKey, search searchKey, then delete deleteKey (missing deletion is harmless). Duplicates ignored. Returns 1 if search succeeded before deletion, otherwise 0; writes [remaining_count, sorted remaining keys...] to output (capacity at least n+2). Each operation costs O(h), worst-case O(n); total build O(n^2), traversal O(n), auxiliary space O(n). Two-child deletion uses the inorder successor. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation.
function algorithm(a, n, insertKey, searchKey, deleteKey, output) {
    let keys = Array(256).fill(0); let left = Array(256).fill(0); let right = Array(256).fill(0); let stack = Array(256).fill(0);
    let root = -1; let count = 0; let u = 0; let parent = -1; let value = 0; let found = 0; let successor = 0; let successorParent = 0; let child = 0; let top = 0; let length = 0;
    for (let i = 0; i < 8; i++) { left[i] = -1; right[i] = -1; }
    for (let i = 0; i <= n; i++) {
        value = insertKey; if (i < n) { value = a[i]; }
        u = root; parent = -1;
        while (u >= 0 && keys[u] != value) { parent = u; if (value < keys[u]) { u = left[u]; } else { u = right[u]; } }
        if (u >= 0) { continue; }
        keys[count] = value;
        if (parent < 0) { root = count; } else if (value < keys[parent]) { left[parent] = count; } else { right[parent] = count; }
        count++;
    }
    u = root;
    while (u >= 0 && keys[u] != searchKey) { if (searchKey < keys[u]) { u = left[u]; } else { u = right[u]; } }
    if (u >= 0) { found = 1; }
    u = root; parent = -1;
    while (u >= 0 && keys[u] != deleteKey) { parent = u; if (deleteKey < keys[u]) { u = left[u]; } else { u = right[u]; } }
    if (u >= 0) {
        if (left[u] >= 0 && right[u] >= 0) {
            successorParent = u; successor = right[u];
            while (left[successor] >= 0) { successorParent = successor; successor = left[successor]; }
            keys[u] = keys[successor]; parent = successorParent; u = successor;
        }
        child = left[u]; if (child < 0) { child = right[u]; }
        if (parent < 0) { root = child; } else if (left[parent] == u) { left[parent] = child; } else { right[parent] = child; }
    }
    u = root;
    while (u >= 0 || top > 0) {
        while (u >= 0) { stack[top++] = u; u = left[u]; }
        u = stack[--top]; output[++length] = keys[u]; u = right[u];
    }
    output[0] = length;
    return found;
}

Source

Historical primary research on binary search trees and changing searchable lists. The playground demonstrates ordinary insertion, search and successor-based deletion, not a balanced tree.