Arrays and linked lists line data up in a row. Trees branch out, and that one change makes searching dramatically faster. The binary search tree (BST) is the tree every exam and interview starts with, along with the three traversals everyone mixes up: inorder, preorder and postorder.
In this guide you'll grow your own BST, watch searches take the short path, step through every traversal, learn the delete cases, and pick up a memory trick that makes the traversals impossible to confuse.
What is a tree in data structure?
A tree is a hierarchical data structure: one node at the top (the root), and every other node has exactly one parent. Think of a family tree, folders on your laptop, or the HTML of this page. The terms you need:
| Root | The top node; it has no parent (50 above). |
| Parent / child | A node directly above / below another (30 is the parent of 20 and 40). |
| Leaf | A node with no children (20, 40, 60, 80). |
| Subtree | A node plus everything below it. |
| Depth of a node | Number of edges from the root to it (root has depth 0). |
| Height of a tree | Number of edges on the longest root-to-leaf path. |
| Binary tree | Every node has at most 2 children: left and right. |
Notice that each child is the root of a smaller tree. That's why trees and recursion fit together perfectly: handle this node, then recurse on the left and right subtrees.
What makes it a binary search tree?
One rule, applied at every node:
- Everything in the left subtree is smaller than the node.
- Everything in the right subtree is bigger than the node.
So searching works exactly like binary search: compare with the current node and throw away half of what's left. Insert some numbers and search for them:
🎮 BST playground
7 nodes · height 2 (edges)Type a number, then Insert it or Search for it. Watch which way it goes at each node.
Tree traversals: inorder, preorder, postorder
A traversal visits every node exactly once. The three depth-first traversals differ only in when you visit the parent compared with its children (children are always left before right). Step through each one:
🚶 Tree traversal, step by step
Left → Root → Right. In a BST this gives the values in sorted order.
Inorder: …
🧠 PATH memory card
Remember BSTs and traversals for good
Picture it · Anchor it · Trace it · Hit-recall it. Four quick steps that turn “I read it once” into “I can explain it in an exam”.
- P
Picture it
Your brain remembers scenes far better than definitions.
← swipe to see the whole picture →
A mango orchard where every fork has the same signboard: “◀ small · big ▶”. To find tree 40, turn left at 50 and right at 30. And three friends remember the walks by when they greet the parent: PRE first, IN in between, POST last.
- A
Anchor it
A silly sentence you can't forget, where every word maps to the concept.
“Left Small, Right Big; IN-order comes out sorted”
- Left Small→Left subtree values are smaller
- Right Big→Right subtree values are bigger
- Signboard at every fork→The rule holds at every node, not just the root
- PRE→Parent first: root, left, right
- IN→Parent in between: left, root, right → sorted
- POST→Parent last: left, right, root
- T
Trace it
Run it by hand on a tiny example once. Doing beats reading.
Tree: 50 with children 30 (20, 40) and 70 (60, 80). Pre: 50 30 20 40 70 60 80. In: 20 30 40 50 60 70 80 (sorted ✓). Post: 20 40 30 60 80 70 50 (root last ✓). Say it: “pre starts with the root, post ends with the root, in comes out sorted.” - H
Hit-recall it
Test yourself now, then again on the day each card comes back.
Card 1 / 9 · new0 mastered · 0 practisedSay the answer out loud first, then flip and be honest.
Deleting a node from a BST
Insert and search are easy. Delete has three cases, and exams love asking for all three:
- Leaf (no children): just remove it. Deleting 20 above leaves 30 with only 40.
- One child: connect the parent directly to that child, skipping the deleted node.
- Two children: find the inorder successor (the smallest value in the right subtree: go right once, then left as far as possible). Copy its value into the node, then delete the successor, which has at most one child. Deleting 50 above puts 60 at the root.
BST implementation in Python, Java and C++
Insert, search, delete with all three cases, and the traversals, using the same tree as the demos.
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def insert(root, val): # O(h)
if root is None:
return Node(val)
if val < root.val:
root.left = insert(root.left, val)
elif val > root.val:
root.right = insert(root.right, val)
return root
def search(root, val): # O(h)
while root and root.val != val:
root = root.left if val < root.val else root.right
return root is not None
def delete(root, val): # O(h)
if root is None:
return None
if val < root.val:
root.left = delete(root.left, val)
elif val > root.val:
root.right = delete(root.right, val)
else:
if root.left is None: # 0 or 1 child
return root.right
if root.right is None:
return root.left
succ = root.right # 2 children: inorder successor
while succ.left:
succ = succ.left
root.val = succ.val
root.right = delete(root.right, succ.val)
return root
def inorder(root): # left, root, right -> sorted
return inorder(root.left) + [root.val] + inorder(root.right) if root else []
def preorder(root): # root, left, right
return [root.val] + preorder(root.left) + preorder(root.right) if root else []
def postorder(root): # left, right, root
return postorder(root.left) + postorder(root.right) + [root.val] if root else []
root = None
for v in [50, 30, 70, 20, 40, 60, 80]:
root = insert(root, v)
print(inorder(root)) # [20, 30, 40, 50, 60, 70, 80]
print(preorder(root)) # [50, 30, 20, 40, 70, 60, 80]
print(postorder(root)) # [20, 40, 30, 60, 80, 70, 50]
print(search(root, 60)) # True
root = delete(root, 30)
print(inorder(root)) # [20, 40, 50, 60, 70, 80]Time complexity of BST operations
| Operation | Balanced BST | Skewed BST (worst) |
|---|---|---|
| Search | O(log n) | O(n) |
| Insert | O(log n) | O(n) |
| Delete | O(log n) | O(n) |
| Find min / max | O(log n) | O(n) |
| Traversal (any order) | O(n) | O(n) |
BST vs hash table: which one?
A hash table is faster for plain lookups (O(1) vs O(log n)). Choose a balanced BST when you need order: the smallest or largest key, all keys in a range, the next bigger key, or the keys in sorted order.
Common BST interview questions
- Validate a BST: do an inorder traversal and check it's strictly increasing (or pass min/max bounds down).
- Height of a tree:
1 + max(height(left), height(right)), with an empty tree at height −1 or 0 by convention. - Lowest common ancestor in a BST: walk down from the root; the first node between the two values is the answer.
- k-th smallest element: inorder traversal, stop at the k-th node.
What to learn next
A tree is a special kind of graph: connected, with no cycles. Next in the course, drop those limits and explore any network with graphs, BFS and DFS. Level-order traversal above was your first taste of BFS.
Key takeaways
- ✓A tree is a hierarchy: one root, and every other node has exactly one parent.
- ✓BST rule at every node: left subtree smaller, right subtree bigger.
- ✓Search, insert and delete are O(h): O(log n) balanced, O(n) skewed.
- ✓Preorder = parent first, inorder = parent in between (sorted), postorder = parent last.
- ✓Delete with two children: replace with the inorder successor.
- ✓Remember it with “Left Small, Right Big; IN-order comes out sorted.”
Frequently asked questions
What is a binary search tree?
A binary search tree (BST) is a binary tree where, for every node, all values in its left subtree are smaller and all values in its right subtree are larger. This ordering lets you search, insert and delete by going left or right at each node, like binary search on a sorted array.
What is the difference between a binary tree and a binary search tree?
A binary tree only limits each node to at most two children; values can be in any order. A binary search tree adds the ordering rule: left subtree smaller, right subtree larger. Every BST is a binary tree, but not every binary tree is a BST.
What are inorder, preorder and postorder traversals?
They are depth-first ways to visit every node. Preorder visits root, left, right (parent first). Inorder visits left, root, right (parent in between), which prints a BST in sorted order. Postorder visits left, right, root (parent last). Level order visits level by level using a queue.
What is the time complexity of BST operations?
Search, insert and delete take O(h), where h is the height of the tree. In a balanced BST, h is about log n, so operations are O(log n). If values are inserted in sorted order the tree becomes a chain with h = n, and operations degrade to O(n).
How do you delete a node from a BST?
Three cases. A leaf: just remove it. A node with one child: replace it with that child. A node with two children: replace its value with its inorder successor (the smallest value in its right subtree), then delete that successor node, which has at most one child.
🧠 Quick check: binary search trees
1. Insert 50, 30, 70, 40 into an empty BST. Where does 40 go?
2. Which traversal prints a BST's values in sorted order?
3. What is the worst-case search time in an unbalanced BST with n nodes?
4. In the PATH anchor, what does POST mean?
Checking your access…