Binary Search Tree (BST)
Software Engineer path · lesson 16 of 99A hierarchical data structure where each node has at most two children. For any node, the left child is smaller and the right child is larger, allowing for efficient O(log n) average-case search, insertion, and deletion (this degrades to O(n) on an unbalanced tree).
Syntax: insert n · search n · delete n · inorder · preorder · postorder · levelorder. Numbers from -99 to 99.
Empty tree
Empty tree. Run the operations in order.
- 1insert(x): node = root
- 2 while node: node = node.left if x < node.val else node.right
- 3 attach x where the walk fell off the tree
- 4search(x): walk the same way; stop when node.val == x
- 5delete(x): find x
- 6 0 or 1 child: replace x with that child
- 7 2 children: copy the in-order successor into x, delete the successor
- 8traverse: in-order (L, node, R) · pre-order (node, L, R) · post-order (L, R, node) · level-order (queue)
- Comparisons
- 0 / 15
height 0, 0 nodes
Tap any element in the diagram to inspect its state at this step.
Keys: ← → step, Space play/pause. Predict mode pauses before key steps and asks what happens next.
In-order traversal
Keys 50, 30, 70, 20, 40 were inserted into an empty BST. Order the keys as an in-order traversal visits them.
Tap a piece, then tap where it goes — or drag it. Tap the tray to take one back.
- 1Drop a step here
- 2Drop a step here
- 3Drop a step here
- 4Drop a step here
- 5Drop a step here
Test your knowledge
What is the worst-case time complexity of searching in a BST?
When to reach for this
- When you need to maintain a **Sorted** collection
- When you need fast Lookup, Insert, and Delete (O(log n))
- Finding the closest value, floor, or ceiling
Interview Questions
References & Further Reading
Love this visualization?
Sign up to track your progress, earn achievements, use the AI assistant, and access your personal learning dashboard.
100% free • No credit card required