Got it!
Here’s a simple Python program to construct a Binary Search Tree (BST) using classes and
objects, focusing on keeping the inner workings straigh orward:
Python Program for BST:
# Define a Node class to represent each node in the tree
class Node:
def __init__(self, key):
self.key = key
self.le = None
self.right = None
# Define a BST class to manage the tree opera ons
class BST:
def __init__(self):
self.root = None
def insert(self, key):
# If the tree is empty, set the root to be a new node
if self.root is None:
self.root = Node(key)
else:
# Insert the new node in the correct posi on
self._insert(self.root, key)
def _insert(self, current_node, key):
# If the new key is less than the current node's key, go le
if key < current_node.key:
if current_node.le is None:
current_node.le = Node(key)
else:
self._insert(current_node.le , key)
# If the new key is greater than or equal to the current node's key, go right
else:
if current_node.right is None:
current_node.right = Node(key)
else:
self._insert(current_node.right, key)
def in_order_traversal(self):
# List to store the traversal result
result = []
self._in_order_traversal(self.root, result)
return result
def _in_order_traversal(self, node, result):
if node:
# Traverse the le subtree
self._in_order_traversal(node.le , result)
# Visit the root
result.append(node.key)
# Traverse the right subtree
self._in_order_traversal(node.right, result)
def pre_order_traversal(self):
# List to store the traversal result
result = []
self._pre_order_traversal(self.root, result)
return result
def _pre_order_traversal(self, node, result):
if node:
# Visit the root
result.append(node.key)
# Traverse the le subtree
self._pre_order_traversal(node.le , result)
# Traverse the right subtree
self._pre_order_traversal(node.right, result)
def post_order_traversal(self):
# List to store the traversal result
result = []
self._post_order_traversal(self.root, result)
return result
def _post_order_traversal(self, node, result):
if node:
# Traverse the le subtree
self._post_order_traversal(node.le , result)
# Traverse the right subtree
self._post_order_traversal(node.right, result)
# Visit the root
result.append(node.key)
# Example usage
bst = BST()
numbers = [8, 4, 12, 2, 6, 10, 14, 1, 3, 5]
# Insert numbers into the BST
for num in numbers:
bst.insert(num)
# Perform and print the different traversals
print("In-order Traversal:", bst.in_order_traversal())
print("Pre-order Traversal:", bst.pre_order_traversal())
print("Post-order Traversal:", bst.post_order_traversal())
Explana on:
1. Node Class: Represents each node in the BST.
o __init__(self, key): Ini alizes a node with a key and le /right pointers set to None.
2. BST Class: Manages the BST opera ons.
o __init__(self): Ini alizes the tree with an empty root.
o insert(self, key): Inserts a key into the BST. Calls _insert() to handle the actual
inser on logic.
o _insert(self, current_node, key): Helper method to insert a key in the correct
posi on.
o in_order_traversal(self): Returns a list of keys from an in-order traversal.
Calls _in_order_traversal() to perform the traversal.
o _in_order_traversal(self, node, result): Helper method for in-order traversal.
o pre_order_traversal(self): Returns a list of keys from a pre-order traversal.
Calls _pre_order_traversal() to perform the traversal.
o _pre_order_traversal(self, node, result): Helper method for pre-order traversal.
o post_order_traversal(self): Returns a list of keys from a post-order traversal.
Calls _post_order_traversal() to perform the traversal.
o _post_order_traversal(self, node, result): Helper method for post-order traversal.
Traversal Outputs:
In-order Traversal: Visits nodes in ascending order.
Pre-order Traversal: Visits nodes star ng from the root, then le subtree, followed by right
subtree.
Post-order Traversal: Visits nodes star ng from the le subtree, then right subtree, followed
by the root.
This program constructs a BST from the given set of numbers and performs different traversals to
display the order of nodes. If you have any more ques ons or need further details, feel free to ask!
