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

Similar Programs Chapter Last Updated
Python Program To Replace Characters In A String Python 03-06-2023
Python Program To Replace Blank Space With Hyphen Python 30-05-2023
Python Regex Match End Of String Python 30-05-2023
Python Check If String Contains Certain Characters Python 30-05-2023
How To Get The Length Of An Array In Python Python 27-05-2023
How To Find The First Duplicate Element In A Given Array Of Integers In Python Python 27-05-2023
How To Get Key And Value From Dictionary In Python Python 24-05-2023
Merge Two Dictionaries In Python Python 24-05-2023
Convert Two Lists Into A Dictionary In Python Python 24-05-2023
How To Remove An Element From A Set In Python Python 19-05-2023
Return A New Set Of Identical Items From Two Sets In Python Python 19-05-2023
Add A List Of Elements To A Set In Python Python 19-05-2023
Check If Two Lists Have At-least One Element Common In Python Python 17-05-2023
Python Program To Remove All The Occurrences Of An Element From A List Python 17-05-2023
Write A Python Program To Turn Every Item Of A List Into Its Square Python 15-05-2023
Write A Python Program To Concatenate Two Lists Index-wise Python 15-05-2023
Write A Python Program To Reverse A List Python 15-05-2023
How To Run Python Program In Terminal Python 14-05-2023
Python Date Format AM PM Python 14-05-2023
Python Add Months To Date Example Python 14-05-2023
Python Add Days To Date Example Python 14-05-2023
Python List All Elements In List Python 30-04-2023
Python Program To Check Prime Number Using Function Python 27-04-2023
Python Program To Sum All The Items In A List Python 27-04-2023
Python Interest Calculator Python 27-04-2023
Python Program To Print Calendar Of Any Year Python 26-04-2023
Python Program To Print Calendar Python 26-04-2023
How To Create XML File In Python Python 23-04-2023
Python Run Function At Specific Time Everyday Python 22-04-2023
Python Program For String Reverse Python 20-04-2023

1 2 3