Binary Search Tree (BST) Implementations
1. Iterative BST Implementation
- Node Class:
- Represents a single node in the tree with
data, left, and right pointers.
- Insertion:
- If the tree is empty, the node becomes the root.
- Traverse the tree iteratively:
- Move left if the value is smaller than the current node.
- Move right if the value is larger.
- Insert the value when a
None position is found.
- Search:
- Traverse the tree iteratively:
- If the value matches the current node, return
True.
- Move left or right based on comparisons.
- Return
False if the value isn’t found before reaching a leaf.
- Traversals:
- Inorder: Left → Root → Right.
- Preorder: Root → Left → Right.
- Postorder: Left → Right → Root.
- Reverse: Right → Left → Root.
- Maximum/Minimum:
- For maximum, move right until the last node.
- For minimum, move left until the last node.
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
class BST:
def __init__(self):
self.root = None
def insert(self, data):
node = Node(data)
if self.root is None:
self.root = node
return
else:
cur = self.root
while cur:
if cur.data > data:
if cur.left is None:
cur.left = node
return
else:
cur = cur.left
else:
if cur.right is None:
cur.right = node
return
else:
cur = cur.right
def search(self, data):
if self.root is None:
return 'empty bst'
else:
cur = self.root
while cur:
if cur.data == data:
return True
elif cur.data > data:
if cur.left is None:
return False
else:
cur = cur.left
else:
if cur.right is None:
return False
else:
cur = cur.right
def inorder(self):
def helper(node):
if node:
helper(node.left)
print(node.data, end=' ')
helper(node.right)
helper(self.root)
print()
def preorder(self):
def helper(node):
if node:
print(node.data, end=' ')
helper(node.left)
helper(node.right)
helper(self.root)
print()
def postorder(self):
def helper(node):
if node:
helper(node.left)
helper(node.right)
print(node.data, end=' ')
helper(self.root)
print()
def reverse(self):
def helper(node):
if node:
helper(node.right)
helper(node.left)
print(node.data, end=' ')
helper(self.root)
print()
def maximum(self):
cur = self.root
while cur:
if cur.right is None:
return cur.data
else:
cur = cur.right
def minimum(self):
cur = self.root
while cur:
if cur.left is None:
return cur.data
else:
cur = cur.left
bst = BST()
values = [50, 30, 80, 10, 40, 90, 60]
for value in values:
bst.insert(value)
print(bst.search(10)) # True
print(bst.search(70)) # False
bst.inorder() # 10 30 40 50 60 80 90
bst.preorder() # 50 30 10 40 80 60 90
bst.postorder() # 10 40 30 60 90 80 50
bst.reverse() # 90 80 60 50 40 30 10
print(bst.maximum()) # 90
print(bst.minimum()) # 10
---------------------------------------
True
False
10 30 40 50 60 80 90
50 30 10 40 80 60 90
10 40 30 60 90 80 50
90 80 60 50 40 30 10
90
10
2. Recursive BST Implementation
- Insertion:
- Compare the value with the root:
- If smaller, recursively insert into the left subtree.
- If larger, recursively insert into the right subtree.
- Search:
- Base Case 1: If the target matches the current node, return
"Found".
- Base Case 2: If the subtree is
None, return "Not found".
- Recursive Cases:
- Go left if the target is smaller.
- Go right if the target is larger.
- Traversals:
- Inorder: Recursive left → Print root → Recursive right.
- Preorder: Print root → Recursive left → Recursive right.
- Postorder: Recursive left → Recursive right → Print root.
- Reverse: Recursive right → Print root → Recursive left.
- Maximum/Minimum:
- Move right for maximum until no further subtree exists.
- Move left for minimum until no further subtree exists.
class BST:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def insert(self, value):
if value < self.data:
if self.left is None:
self.left = BST(value)
else:
self.left.insert(value)
else:
if self.right is None:
self.right = BST(value)
else:
self.right.insert(value)
def search(self, target):
if self.data == target:
return "Found"
elif target < self.data:
if self.left is None:
return "Not found"
else:
return self.left.search(target)
else:
if self.right is None:
return "Not found"
else:
return self.right.search(target)
def inorder(self):
if self.left:
self.left.inorder()
print(self.data, end=' ')
if self.right:
self.right.inorder()
def preorder(self):
print(self.data, end=' ')
if self.left:
self.left.preorder()
if self.right:
self.right.preorder()
def postorder(self):
if self.left:
self.left.postorder()
if self.right:
self.right.postorder()
print(self.data, end=' ')
def minimum(self):
if self.left is None:
print(self.data)
else:
self.left.minimum()
def maximum(self):
if self.right is None:
print(self.data)
else:
self.right.maximum()
# main
bst = BST(50)
values = [30, 80, 10, 40, 90, 60]
for value in values:
bst.insert(value)
print(bst.search(10)) # Found
print(bst.search(70)) # Not found
bst.inorder() # 10 30 40 50 60 80 90
print()
bst.preorder() # 50 30 10 40 80 60 90
print()
bst.postorder() # 10 40 30 60 90 80 50
print()
bst.minimum() # 10
bst.maximum() # 90
---------------------------------------
Found
Not found
10 30 40 50 60 80 90
50 30 10 40 80 60 90
10 40 30 60 90 80 50
10
90
3. Array-Based BST Implementation
- Concept: Use an array to simulate a BST:
- The root is at index 0.
- The left child of a node at index
i is at 2*i + 1.
- The right child of a node at index
i is at 2*i + 2.
- Insertion:
- If the position exceeds the array size, insertion isn’t possible.
- Recursively decide to go left (
2*i + 1) or right (2*i + 2).
- Search:
- Base Case 1: If the index is out of bounds or the slot is
None, return "Not found".
- Base Case 2: If the target matches the value at the index, return
"Found".
- Recursive Cases:
- Go left (
2*i + 1) if the target is smaller.
- Go right (
2*i + 2) if the target is larger.
- Traversals:
- Inorder: Recursive left → Current node → Recursive right.
- Preorder: Current node → Recursive left → Recursive right.
- Postorder: Recursive left → Recursive right → Current node.
- Maximum/Minimum:
- For maximum, move to the right child (
2*i + 2) until no further right exists.
- For minimum, move to the left child (
2*i + 1) until no further left exists.
class BST:
def __init__(self, size):
self.size = size
self.tree = [None] * size
self.root = 0
def insert(self, value, index=0):
if index >= self.size:
print(f"Cannot insert {value}: Index {index} out of bounds")
return
if self.tree[index] is None:
self.tree[index] = value
elif value < self.tree[index]:
self.insert(value, 2 * index + 1)
else:
self.insert(value, 2 * index + 2)
def search(self, target, index=0):
if index >= self.size or self.tree[index] is None:
return "Not found"
if self.tree[index] == target:
return "Found"
elif target < self.tree[index]:
return self.search(target, 2 * index + 1)
else:
return self.search(target, 2 * index + 2)
def inorder(self, index=0):
if index < self.size and self.tree[index] is not None:
self.inorder(2 * index + 1)
print(self.tree[index], end=' ')
self.inorder(2 * index + 2)
def preorder(self, index=0):
if index < self.size and self.tree[index] is not None:
print(self.tree[index], end=' ')
self.preorder(2 * index + 1)
self.preorder(2 * index + 2)
# main
bst = BST(7)
values = [50, 30, 70, 20, 40, 60, 90]
for value in values:
bst.insert(value)
print(bst.search(10)) # Not found
print(bst.search(70)) # Found
bst.inorder() # 20 30 40 50 60 70 90
print()
bst.preorder() # 50 30 20 40 70 60 90
print()
---------------------------------------
Not found
Found
20 30 40 50 60 70 90
50 30 20 40 70 60 90