Trees
Tree data structure is a hierarchical structure that is used to represent and organize data in a way that is easy to navigate and search. It is a collection of nodes that are connected by edges and has a hierarchical relationship between the nodes.
There various types of trees:
-Binary Tree: A tree in which each node has at most 2 children nodes.
-Ternary Tree: A tree in which each node has at most 3 children nodes.
-N-ary Tree: A tree in which each node has at most N children nodes.
In this post, we will be covering Binary Search Trees and the method to insert values, In-order traversal as well as delete a node.
What is a Binary Search Tree?
A binary search tree is a hierarchical data structure where each node has at most two children, with values ordered such that left child values are smaller and right child values are greater.
A Binary Search Tree can be visualized by the following image:
Creating a Binary Search Tree
Before creating the Binary Search Tree, we first need to define the Node class. As mentioned in the previous posts, a Node contains data which is the value to be stored, and two pointers. Here one pointer called as left is used to point to the left child and the other called right is used to point to the right child. We specify the left and right as None as when we add a node it doesn't have children yet.
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
Now we have created the class Node, we can now proceed in working with the BinarySearchTree class. In the tree class, we will modify the constructor or __init__(self) to automatically create the root node.
class BinarySearchTree:
def __init__(self):
self.root = Node(None)
Now in this class we will specify methods to insert a node, in this method we accept a key or value to be inserted. We will then create a node. Now we first check if we have a root node , if we do not, ie, root is None then we make this newly created node as the root. Otherwise, we iterate from the root node and compare the input data value to the key. If it's greater than the key, we move to the left child, if it's lesser, we move to the right child and if we come to the leaf node, depending on the comparison, we will add this node as the left or right child respectively.
def insert(self, key):
node = Node(key)
if self.root is None:
self.root = node
return
prev = None
temp = self.root
while temp is not None:
if temp.data > key:
prev = temp
temp = temp.left
elif temp.data < key:
prev = temp
temp = temp.right
if prev.data > key:
prev.left = node
else:
prev.right = node
Traversal
In this process, we move through the Binary Search Tree in a specific way. There various Traversal Methods are:
-In-order: In which for each node in the tree, we first visit the left child, then the node and then it's right child.
-Pre-order: In which for each node in the tree, we first visit the node, then the node's left child and then it's right child.
-Post-order: In which for each node in the tree, we first visit the node's left child and then it's right child and then the node itself.
In-order traversal
In, in-order traversal , we essentially first recursively iterate through the left sub-tree and once we reach the leaf, since the node has no left child, the data of the node is printed, and since the node does not have right child, we go back to the previous call (which called on the left sub-tree) and then we print that node's data and then call it's right sub-tree. The logic applies the same and this repeats till we reach the right most node of the tree.
def inorder(self, node):
if node is not None:
self.inorder(node.left)
print(str(node.data) + " ", end="") #to print on same line
self.inorder(node.right)
Delete
So when we delete a node, we first find the node which contains the key or the data to be deleted by recursively calling the left/right sub-tree based if the key is lower/higher than the current node respectively. When the key matches the node data , if the node does not hava a left child, we iterate it's right child, and if does not have a right child, we iterate it's left child and if has both, we find the minimum of the right sub-tree so that we can replace the node's data with the minimum data, resulting in a duplicate, and we recursively call the function, with the node to be deleted as the root, and it's data as the key. Till it reaches a leaf node and as a result returns None. Indicating the node is deleted.
def deleteNode(self, root, key):
if root is None:
return root
if key < root.data:
root.left = self.deleteNode(root.left, key)
elif key > root.data:
root.right = self.deleteNode(root.right, key)
else:
if root.left is None:
return root.right
elif root.right is None:
return root.left
root.data = self.minValue(root.right)
root.right = self.deleteNode(root.right, root.data)
return root
def minValue(self, node):
current = node
while current.left is not None:
current = current.left
return current.data
The full code to implement the Binary Search Tree is provided below.
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, key):
node = Node(key)
if self.root is None:
self.root = node
return
prev = None
temp = self.root
while temp is not None:
if temp.data > key:
prev = temp
temp = temp.left
elif temp.data < key:
prev = temp
temp = temp.right
if prev.data > key:
prev.left = node
else:
prev.right = node
def inorder(self, node):
if node is not None:
self.inorder(node.left)
print(str(node.data) + " ", end="")
self.inorder(node.right)
def deleteNode(self, root, key):
if root is None:
return root
if key < root.data:
root.left = self.deleteNode(root.left, key)
elif key > root.data:
root.right = self.deleteNode(root.right, key)
else:
if root.left is None:
return root.right
elif root.right is None:
return root.left
root.data = self.minValue(root.right)
root.right = self.deleteNode(root.right, root.data)
return root
def minValue(self, node):
current = node
while current.left is not None:
current = current.left
return current.data
bst = BinarySearchTree()
while True:
print("\nBinary Search Tree Menu:")
print("1. Insert")
print("2. Display All Values")
print("3. Delete")
print("4. Exit")
choice = input("Enter choice: ")
if choice == '1':
data = int(input("Enter data: "))
bst.insert(data)
print(f"{data} has been inserted.")
elif choice == '2':
bst.inorder(bst.root)
elif choice == '3':
data = int(input("Enter the data: "))
bst.root = bst.deleteNode(bst.root, data)
print(f"{data} has been deleted.")
elif choice == '4':
break
else:
print("Invalid choice")
NOTE:
If you're finding it a bit hard to visualize how the Binary Search Tree works, here is a very helpful website that does it for you.
Top comments (0)