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.
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.
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": [] }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": [] }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": [] }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": [] }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:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
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.
- Some Combinatorial Properties of Certain Trees With Applications to Searching and Sorting
Thomas N. Hibbard (1962). Historical research paper.