In this tutorial, we will learn how to implement a Binary Search Tree (BST) in Python. A BST is a data structure that stores items in a sorted manner and allows efficient operations like insertion, search, and deletion. By the end of this tutorial, you will have a clear understanding of how to create, modify, and traverse a BST using Python.
To follow along with this tutorial, you should have a basic understanding of Python programming language concepts, including variables, functions, and classes. Familiarity with data structures, such as linked lists and arrays, will also be helpful.
There is no additional setup required to implement a Binary Search Tree in Python. We’ll be using only the built-in data structures and functions provided by the Python language.
Let’s start by creating a class called Node that represents a single node in the BST. Each node will contain a key (the value it holds), a left child, and a right child. We’ll also define a class called BinarySearchTree that will serve as the BST data structure.
```python
class Node:
def init(self, key):
self.key = key
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
``` In the code above, we define the `Node` class with its constructor that initializes the key, left child, and right child attributes. The `BinarySearchTree` class also has a constructor that initializes the root attribute.
To insert a node into the BST, we need to follow a set of rules:
Let’s implement the insert method in the BinarySearchTree class:
```python
class BinarySearchTree:
# previous code…
def insert(self, key):
new_node = Node(key)
if self.root is None:
self.root = new_node
else:
current = self.root
while True:
if key < current.key:
if current.left is None:
current.left = new_node
return
current = current.left
else:
if current.right is None:
current.right = new_node
return
current = current.right
``` In the code above, we create a new node with the provided key. If the tree is empty (root is None), we set the new node as the root. Otherwise, we traverse the tree using a while loop, comparing the key with the current node's key until we find an empty spot to insert the new node.
Searching for a specific key in the Binary Search Tree follows a similar approach to inserting:
Let’s implement the search method in the BinarySearchTree class:
```python
class BinarySearchTree:
# previous code…
def search(self, key):
current = self.root
while current is not None:
if key == current.key:
return current
elif key < current.key:
current = current.left
else:
current = current.right
return None
``` In the code above, we start from the root and traverse the tree until we find the node with the matching key or reach a leaf node.
Deleting a node from a Binary Search Tree is a bit more complex. There are three possible cases to handle:
Let’s implement the delete method in the BinarySearchTree class:
```python
class BinarySearchTree:
# previous code…
def delete(self, key):
def find_min(node):
current = node
while current.left:
current = current.left
return current
def delete_node(root, key):
if root is None:
return root
if key < root.key:
root.left = delete_node(root.left, key)
elif key > root.key:
root.right = delete_node(root.right, key)
else:
if root.left is None:
return root.right
elif root.right is None:
return root.left
temp = find_min(root.right)
root.key = temp.key
root.right = delete_node(root.right, temp.key)
return root
self.root = delete_node(self.root, key)
``` In the code above, we define two helper functions: `find_min` to find the node with the minimum key value in a given sub-tree, and `delete_node` to handle the deletion process recursively.
Now that we have implemented the core functionalities of a Binary Search Tree, let’s explore traversal techniques to visit all the nodes in the tree.
In-order traversal visits the left child, then the current node, and finally the right child. ```python class BinarySearchTree: # previous code…
def inorder(self, node):
if node is None:
return
self.inorder(node.left)
print(node.key)
self.inorder(node.right)
``` In the code above, we define the `inorder` method that recursively visits the left sub-tree, prints the current node's key, and then recursively visits the right sub-tree.
Pre-order traversal visits the current node, then the left child, and finally the right child. ```python class BinarySearchTree: # previous code…
def preorder(self, node):
if node is None:
return
print(node.key)
self.preorder(node.left)
self.preorder(node.right)
``` In the code above, we define the `preorder` method that prints the current node's key, recursively visits the left sub-tree, and then recursively visits the right sub-tree.
Post-order traversal visits the left child, then the right child, and finally the current node. ```python class BinarySearchTree: # previous code…
def postorder(self, node):
if node is None:
return
self.postorder(node.left)
self.postorder(node.right)
print(node.key)
``` In the code above, we define the `postorder` method that recursively visits the left sub-tree, recursively visits the right sub-tree, and then prints the current node's key.
In this tutorial, we learned how to implement a Binary Search Tree (BST) in Python. We explored the concepts of inserting nodes, searching for a specific key, deleting nodes, and traversing the tree using in-order, pre-order, and post-order techniques.
By understanding and implementing a BST, you can efficiently store and retrieve sorted data. This knowledge is essential in various application domains, such as searching, sorting, and data analytics.
Feel free to experiment with the code and explore additional functionalities to enhance the BST implementation. Happy coding!