Binary Search Tree
Here is the definition of BST:
- The parent is always greater than its left child.
- The parent is always smaller than or equal to its right child.
Implementation
Here is a basic interface for a BST. We can add and remove values, and this BST also has three traversal methods.
# Implement your BST here
class Node:
def __init__(self, value):
raise NotImplementedError
class BinarySearchTree:
def __init__(self):
raise NotImplementedError
def insert(self, value):
raise NotImplementedError
def remove(self, value):
raise NotImplementedError
def search(self, value):
raise NotImplementedError
def preorder(self):
raise NotImplementedError
def inorder(self):
raise NotImplementedError
def postorder(self):
raise NotImplementedError
Node Implementation.
A node in the BST must have 3 attributes at least, its value and left/right pointers.
from typing import Self, Any
class Node:
def __init__(self, value):
self._value = value
self._right: Self | None = None
self._left: Self | None = None
@property
def value(self) -> Any:
return self._value
@value.setter
def value(self, value):
self._value = value
@property
def right(self) -> Self | None:
return self._right
@right.setter
def right(self, node: Self | None) -> Any:
self._right = node
@property
def left(self) -> Self | None:
return self._left
@left.setter
def left(self, node: Self | None) -> Any:
self._left = node
def __repr__(self):
return f"Node(value={self.value})"
I use property getters/setters in this implementation. Python does not have explicit getter/setter methods (or public/private keywords). However, there are useful decorators to create read-only or editable attributes. documentation
Adding a new value
To add a new value, we need to find a proper position that preserves the BST structure.
def insert(self, value):
new_node = Node(value)
if self._root is None:
self._root = new_node
return
current_node = self._root
while current_node:
if new_node.value >= current_node.value:
if current_node.right:
current_node = current_node.right
else:
current_node.right = new_node
break
else:
if current_node.left:
current_node = current_node.left
else:
current_node.left = new_node
break
If the tree has no elements, just add the new value as the root. Otherwise, we go down to the proper position and insert the new value.
This operation has O(log N) time complexity and O(1) space complexity on average. However, a BST is not necessarily complete or balanced, so the worst case is O(N) time.
Removing a value
Removing a value is a bit more complicated. If the target node to be removed has only 1 child or none, it's easy to remove because just drop the value if the target is a leaf or swap the node if it has a child.
Example:
8 10
\ /
10 => 9
/
9
Remove 8 (has one child). Promote its child (10), then keep the subtree (9).
If the target has two children, how do we remove it while keeping the BST structure? We need to find a successor to insert into the removed node position. That successor must be greater than all values in the left subtree and less than or equal to all values in the right subtree.
So, we need to find the smallest value in the right subtree of the target.
Example:
8
/ \
3 10
/
9
Remove 8. The successor is 9 (the minimum of the right subtree). Replace 8 with 9, then delete the old 9 node.
Here is an implementation of the remove operation.
def remove(self, value):
def _min_node(root: Node) -> Node:
while root.left:
root = root.left
return root
def _delete(root: Node | None, value) -> Node:
if not root:
raise KeyError("Data not found")
if value > root.value:
root.right = _delete(root.right, value)
elif value < root.value:
root.left = _delete(root.left, value)
else:
if root.right is None:
return root.left
if root.left is None:
return root.right
# 2 children case
successor = _min_node(root.right)
root.value = successor.value
root.right = _delete(root.right, successor.value)
return root
self._root = _delete(self._root, value)
Removal needs pointer updates for the parent of the target and its children. If you use a while-loop, you have to remember these pointers to update them. This method uses recursion so the updates are returned as new subtrees, which keeps the logic simpler. Time complexity is O(h) where h is the tree height (O(log N) average, O(N) worst-case). Space complexity is O(h) due to recursion.
Search for a value
Searching for a value in a BST is simple. Traverse the tree by comparing the target with the current node, then move to either child.
def search(self, value):
current = self._root
while current:
if value > current.value:
current = current.right
elif value < current.value:
current = current.left
else:
return True
return False
Time complexity is O(h) where h is the tree height (O(log N) average, O(N) worst-case). Space complexity is O(1) for the iterative version.
Preorder traversal
You visit the root first, then left/right in preorder traversal.
def preorder(self):
def _traverse(root, box):
if root:
box.append(root.value)
_traverse(root.left)
_traverse(root.right)
box = []
_traverse(self._root, box)
return box
Time complexity is O(N) because every node is visited once. Space complexity is O(h) due to the recursion stack.
Preorder is a good choice when the relationship between root and leaves matters. For example, decision trees and ASTs.
Decision tree (preorder lists decisions as you go):
Is it raining?
/ \
Yes No
/ \
Take umbrella Go outside
In-order traversal
You visit left (right) first, then root, and finally right (left) in inorder traversal.
def inorder(self):
def _traverse(root, box):
if root:
_traverse(root.left)
box.append(root.value)
_traverse(root.right)
box = []
_traverse(self._root, box)
return box
Time complexity is O(N) because every node is visited once. Space complexity is O(h) due to the recursion stack.
Inorder is a good choice when sorted order is important. For example, DB indexes (ORDER BY, LIMIT, OFFSET), rankings (top N), or converting an AST into human-readable form.
+
/ \
a b
If inorder is used, the output is:
['a', '+', 'b'] # a + b
DB index (inorder yields sorted keys):
50
/ \
20 70
/ \
60 80
Inorder output: [20, 50, 60, 70, 80]
Ranking (top N from sorted order):
5
/ \
2 9
/ \
7 11
Inorder output: [2, 5, 7, 9, 11], so top 3 are [11, 9, 7].
Post-order traversal
You'll check left/right first, then root.
def postorder(self):
def _traverse(root, box):
if root:
_traverse(root.left)
_traverse(root.right)
box.append(root.value)
box = []
_traverse(self._root, box)
return box
Time complexity is O(N) because every node is visited once. Space complexity is O(h) due to the recursion stack.
Postorder is a good choice when you need children information before processing the root. For example, expression evaluation, memory cleanup, garbage collection, or aggregation.
Expression evaluation:
+
/ \
2 3
Postorder output: [2, 3, +], which evaluates to 5.
Aggregation (sum of subtree):
10
/ \
4 6
Postorder visits 4 and 6 before 10, so you can compute each subtree sum before the parent.
Final implementation
# Implement your BST here
from typing import Self, Any
class Node:
def __init__(self, value):
self._value = value
self._right: Self | None = None
self._left: Self | None = None
@property
def value(self) -> Any:
return self._value
@value.setter
def value(self, value):
self._value = value
@property
def right(self) -> Self | None:
return self._right
@right.setter
def right(self, node: Self | None) -> Any:
self._right = node
@property
def left(self) -> Self | None:
return self._left
@left.setter
def left(self, node: Self | None) -> Any:
self._left = node
def __repr__(self):
return f"Node(value={self.value})"
class BinarySearchTree:
def __init__(self):
self._root: Node | None = None
def insert(self, value):
"""
1. If root is none, use it.
2. if not None, compare the root, if the new value is greater (smaller) than the current node, go right (left). If it's equal, go right.
3. if you find a place to add, add to leaf, if the node is not a leaf, if it has not a leaf, swap with the new node, and add to left or right.
"""
new_node = Node(value)
if self._root is None:
self._root = new_node
return
current_node = self._root
while current_node:
if new_node.value >= current_node.value:
if current_node.right:
current_node = current_node.right
else:
current_node.right = new_node
break
else:
if current_node.left:
current_node = current_node.left
else:
current_node.left = new_node
break
def remove(self, value):
def _min_node(root: Node) -> Node:
while root.left:
root = root.left
return root
def _delete(root: Node | None, value) -> Node:
if not root:
raise KeyError("Data not found")
if value > root.value:
root.right = _delete(root.right, value)
elif value < root.value:
root.left = _delete(root.left, value)
else:
if root.right is None:
return root.left
if root.left is None:
return root.right
# 2 children case
successor = _min_node(root.right)
root.value = successor.value
root.right = _delete(root.right, successor.value)
return root
self._root = _delete(self._root, value)
def search(self, value):
current = self._root
while current:
if value > current.value:
current = current.right
elif value < current.value:
current = current.left
else:
return True
return False
def preorder(self):
results = []
def _preorder_traversal(node: Node):
if node is not None:
results.append(node.value)
_preorder_traversal(node.left)
_preorder_traversal(node.right)
_preorder_traversal(self._root)
return results
def inorder(self):
"""
Search items
1. left first.
2. root.
3. right after.
"""
results = []
def inorder_traversal(node: Node):
if node is not None:
inorder_traversal(node.left)
results.append(node.value)
inorder_traversal(node.right)
inorder_traversal(self._root)
return results
def postorder(self):
results = []
def _postorder_traversal(node: Node):
if node is not None:
_postorder_traversal(node.left)
_postorder_traversal(node.right)
results.append(node.value)
_postorder_traversal(self._root)
return results