Binary Search Tree Implementation Python
Chapter:
Python
Last Updated:
21-03-2023 17:48:14 UTC
Program:
/* ............... START ............... */
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class BST:
def __init__(self):
self.root = None
def insert(self, val):
if not self.root:
self.root = TreeNode(val)
return
curr_node = self.root
while curr_node:
if val < curr_node.val:
if not curr_node.left:
curr_node.left = TreeNode(val)
return
curr_node = curr_node.left
else:
if not curr_node.right:
curr_node.right = TreeNode(val)
return
curr_node = curr_node.right
def search(self, val):
curr_node = self.root
while curr_node:
if val == curr_node.val:
return True
elif val < curr_node.val:
curr_node = curr_node.left
else:
curr_node = curr_node.right
return False
def inorder_traversal(self, node):
if node:
self.inorder_traversal(node.left)
print(node.val)
self.inorder_traversal(node.right)
def preorder_traversal(self, node):
if node:
print(node.val)
self.preorder_traversal(node.left)
self.preorder_traversal(node.right)
def postorder_traversal(self, node):
if node:
self.postorder_traversal(node.left)
self.postorder_traversal(node.right)
print(node.val)
/* ............... END ............... */
Output
bst = BST()
bst.insert(5)
bst.insert(3)
bst.insert(7)
bst.insert(1)
bst.insert(9)
print("Inorder Traversal:")
bst.inorder_traversal(bst.root)
print("Preorder Traversal:")
bst.preorder_traversal(bst.root)
print("Postorder Traversal:")
bst.postorder_traversal(bst.root)
print("Search for 7:", bst.search(7))
print("Search for 8:", bst.search(8))
###############################
Inorder Traversal:
1
3
5
7
9
Preorder Traversal:
5
3
1
7
9
Postorder Traversal:
1
3
9
7
5
Search for 7: True
Search for 8: False
Notes:
-
The program creates a binary search tree object (bst) and inserts several values into it using the insert method. The values inserted are 5, 3, 7, 1, and 9, in that order.
- After inserting the values, the program calls the inorder_traversal, preorder_traversal, and postorder_traversal methods on the binary search tree object bst. Each of these traversal methods visits the nodes of the tree in a different order and prints out the value of each node.
- The search method is also called on the binary search tree object bst to search for the values 7 and 8. The method returns True when searching for 7 (since 7 is in the tree), and False when searching for 8 (since 8 is not in the tree).
- The output shows the result of each traversal method and the result of the two search operations. The inorder traversal shows the values of the nodes in ascending order, the preorder traversal shows the root node before its children, and the postorder traversal shows the root node after its children.
Tags
#Binary search tree Python recursive #Binary Search Tree Implementation Python # Python binary search tree library