Intermediate·1 min read
Binary Search Trees
Efficient searching, insertion, and deletion using BST properties.
Binary Search Trees (BST)
A BST maintains the sorted property: left subtree < node < right subtree.
``
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
``BST Property
For every node N:
- All nodes in N.left have values < N.val
- All nodes in N.right have values > N.val
Operations
| Header | ||
|---|---|---|
| Operation | Average | Worst (skewed) |
| Header | ||
|---|---|---|
| Search | O(log n) | O(n) |
| Insert | O(log n) | O(n) |
| Delete | O(log n) | O(n) |
Deletion Cases
- Leaf node: Just remove it
- One child: Replace with that child
- Two children: Replace with in-order successor (smallest in right subtree), then delete the successor
In-order Successor
The next largest node - found by going right once, then as far left as possible.
Code Example
python
class BSTNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class BST:
def __init__(self):
self.root = None
def insert(self, val):
self.root = self._insert(self.root, val)
def _insert(self, node, val):
if not node:
return BSTNode(val)
if val < node.val:
node.left = self._insert(node.left, val)
elif val > node.val:
node.right = self._insert(node.right, val)
return node
def search(self, val):
return self._search(self.root, val)
def _search(self, node, val):
if not node or node.val == val:
return node
if val < node.val:
return self._search(node.left, val)
return self._search(node.right, val)
def inorder(self):
result = []
self._inorder(self.root, result)
return result
def _inorder(self, node, result):
if node:
self._inorder(node.left, result)
result.append(node.val)
self._inorder(node.right, result)
def delete(self, val):
self.root = self._delete(self.root, val)
def _delete(self, node, val):
if not node:
return None
if val < node.val:
node.left = self._delete(node.left, val)
elif val > node.val:
node.right = self._delete(node.right, val)
else:
if not node.left:
return node.right
if not node.right:
return node.left
successor = node.right
while successor.left:
successor = successor.left
node.val = successor.val
node.right = self._delete(node.right, successor.val)
return node
bst = BST()
for v in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
bst.insert(v)
print("In-order:", bst.inorder())
bst.delete(3)
print("After deleting 3:", bst.inorder())Practice Problems
- 01Validate if a binary tree is a valid BST
- 02Find the kth smallest element in a BST
- 03Convert a sorted array to a balanced BST