Binary Search Tree¶
A from-scratch BST implementation covering insertion, lookup, and four traversal orders, the kind of tree fluency that matters when reasoning about decision trees, hierarchical clustering, or any recursive data structure.
Problem¶
Implement a binary search tree that supports:
- Insert and lookup by key
- Size and height queries
- Traversals: in-order, pre-order, post-order, and level-order (BFS)
Approach¶
The BST maintains the invariant that for every node, all left descendants have smaller keys and all right descendants have larger keys. Each node tracks its subtree size for O(1) size queries.
Insert and lookup recursively walk left or right based on key comparison, O(h) per operation. The four traversals differ only in when they visit the current node: in-order (left, root, right) yields sorted output; pre-order (root, left, right) is useful for serialization; post-order (left, right, root) lets you compute bottom-up, which is exactly how decision tree prediction works; level-order uses a queue to walk the tree top-down, level by level.
Implementation¶
from collections import deque
class Node:
def __init__(self, key, value):
self.key = key
self.value = value
self.left = None
self.right = None
self.size = 1
class BST:
def __init__(self, arr=None):
self.root = None
if arr:
for x in arr:
self.put(x, x)
def size(self):
return self._size(self.root)
def _size(self, node):
return 0 if node is None else node.size
def height(self):
return self._height(self.root)
def _height(self, node):
if node is None:
return 0
return 1 + max(self._height(node.left), self._height(node.right))
def put(self, key, value):
self.root = self._put(key, value, self.root)
def _put(self, key, value, node):
if node is None:
return Node(key, value)
if key == node.key:
node.value = value
elif key < node.key:
node.left = self._put(key, value, node.left)
else:
node.right = self._put(key, value, node.right)
node.size = 1 + self._size(node.left) + self._size(node.right)
return node
def get(self, key):
return self._get(key, self.root)
def _get(self, key, node):
if node is None:
return None
if key == node.key:
return node
elif key < node.key:
return self._get(key, node.left)
else:
return self._get(key, node.right)
def inorder(self):
result = []
self._inorder(self.root, result)
return result
def _inorder(self, node, result):
if node is None:
return
self._inorder(node.left, result)
result.append(node.value)
self._inorder(node.right, result)
def preorder(self):
result = []
self._preorder(self.root, result)
return result
def _preorder(self, node, result):
if node is None:
return
result.append(node.value)
self._preorder(node.left, result)
self._preorder(node.right, result)
def postorder(self):
result = []
self._postorder(self.root, result)
return result
def _postorder(self, node, result):
if node is None:
return
self._postorder(node.left, result)
self._postorder(node.right, result)
result.append(node.value)
def levelorder(self):
if self.root is None:
return []
result = []
queue = deque([self.root])
while queue:
node = queue.popleft()
result.append(node.value)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result
Complexity¶
| Operation | Time (avg) | Time (worst) |
|---|---|---|
| Insert / Lookup | O(log n) | O(n) |
| Traversals | O(n) | O(n) |
| Height | O(n) | O(n) |
- Space: O(n) for the tree; O(h) additional for recursive calls, where h is the height.
Takeaway¶
Understanding how traversal order affects processing order matters more than you'd think. In-order gives you sorted output (useful for range queries), pre-order lets you serialize and reconstruct, post-order lets you compute bottom-up (which is exactly what decision tree prediction does).