[go: up one dir, main page]
Scribd
Upload
30 views6 pages

Program 3 2

The document contains a Python implementation of a Binary Search Tree (BST) with functionalities for inserting, searching, deleting nodes, and performing in-order, pre-order, and post-order traversals. It defines a Node class for tree nodes and a BinarySearchTree class to manage the tree operations. Example usage is provided to demonstrate the operations on the BST.

Uploaded by

D
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
30 views6 pages

Program 3 2

The document contains a Python implementation of a Binary Search Tree (BST) with functionalities for inserting, searching, deleting nodes, and performing in-order, pre-order, and post-order traversals. It defines a Node class for tree nodes and a BinarySearchTree class to manage the tree operations. Example usage is provided to demonstrate the operations on the BST.

Uploaded by

D
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 6

Program 3

WRITE A PROGRAM TO IMPLEMENT ALL


OPERATIONS IN BINARY SEARCH TREE.

class Node:

def __init__(self, key):

self.key = key

self.left = None

self.right = None

class BinarySearchTree:

def __init__(self):

self.root = None

# Insert a node

def insert(self, key):

self.root = self._insert(self.root, key)

def _insert(self, root, key):

if root is None:

return Node(key)

if key < root.key:


root.left = self._insert(root.left, key)

else:

root.right = self._insert(root.right, key)

return root

# Search for a node

def search(self, key):

return self._search(self.root, key)

def _search(self, root, key):

if root is None or root.key == key:

return root

if key < root.key:

return self._search(root.left, key)

return self._search(root.right, key)

# Delete a node

def delete(self, key):

self.root = self._delete(self.root, key)

def _delete(self, root, key):

if root is None:

return root
if key < root.key:

root.left = self._delete(root.left, key)

elif key > root.key:

root.right = self._delete(root.right, key)

else:

# Node with only one child or no child

if root.left is None:

return root.right

elif root.right is None:

return root.left

# Node with two children: Get the inorder successor

temp = self._min_value_node(root.right)

root.key = temp.key

root.right = self._delete(root.right, temp.key)

return root

def _min_value_node(self, node):

current = node

while current.left is not None:

current = current.left

return current

# In-order traversal
def inorder(self):

self._inorder(self.root)

def _inorder(self, root):

if root:

self._inorder(root.left)

print(root.key, end=" ")

self._inorder(root.right)

# Pre-order traversal

def preorder(self):

self._preorder(self.root)

def _preorder(self, root):

if root:

print(root.key, end=" ")

self._preorder(root.left)

self._preorder(root.right)

# Post-order traversal

def postorder(self):

self._postorder(self.root)
def _postorder(self, root):

if root:

self._postorder(root.left)

self._postorder(root.right)

print(root.key, end=" ")

# Example usage

if __name__ == "__main__":

bst = BinarySearchTree()

bst.insert(50)

bst.insert(30)

bst.insert(70)

bst.insert(20)

bst.insert(40)

bst.insert(60)

bst.insert(80)

print("In-order traversal:")

bst.inorder()

print("\nPre-order traversal:")

bst.preorder()

print("\nPost-order traversal:")

bst.postorder()
print("\n\nSearch for 40:", "Found" if bst.search(40) else "Not Found")

print("Search for 90:", "Found" if bst.search(90) else "Not Found")

print("\nDelete 20")

bst.delete(20)

print("In-order traversal after deletion:")

bst.inorder()

Output:

You might also like