1. Tree Algorithms:

Binary Search Tree (BST):

• A binary tree data structure where each node has at most two children, with left children having smaller values and right children having larger values.

class TreeNode:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

class BST:
    def __init__(self):
        self.root = None
    
    def insert(self, key):
        """
        Insert a new key into the BST.
        """
        if self.root is None:
            self.root = TreeNode(key)
        else:
            self._insert_rec(self.root, key)
    
    def _insert_rec(self, root, key):
        """
        Helper function to recursively insert a new key.
        """
        if root is None:
            return TreeNode(key)
        
        if key < root.val:
            root.left = self._insert_rec(root.left, key)
        else:
            root.right = self._insert_rec(root.right, key)
        
        return root
    
    def search(self, key):
        """
        Search for a key in the BST.
        """
        return self._search_rec(self.root, key)
    
    def _search_rec(self, root, key):
        """
        Helper function to recursively search for a key.
        """
        if root is None or root.val == key:
            return root
        
        if key < root.val:
            return self._search_rec(root.left, key)
        else:
            return self._search_rec(root.right, key)
    
    def inorder_traversal(self):
        """
        Perform an inorder traversal of the BST.
        """
        result = []
        self._inorder_rec(self.root, result)
        return result
    
    def _inorder_rec(self, root, result):
        """
        Helper function to recursively perform inorder traversal.
        """
        if root:
            self._inorder_rec(root.left, result)
            result.append(root.val)
            self._inorder_rec(root.right, result)

# Example usage:
bst = BST()
bst.insert(50)
bst.insert(30)
bst.insert(20)
bst.insert(40)
bst.insert(70)
bst.insert(60)
bst.insert(80)

# Perform inorder traversal to retrieve elements in sorted order
print("Inorder traversal:", bst.inorder_traversal())

# Search for a key
key = 70
result = bst.search(key)
if result:
    print(f"Key {key} found in the BST.")
else:
    print(f"Key {key} not found in the BST.")

'''
TreeNode class represents each node in the Binary Search Tree, holding left, right, and val (key) attributes.
BST class implements the Binary Search Tree operations:
insert: Inserts a new key into the BST maintaining the BST property.
search: Searches for a key in the BST.
inorder_traversal: Performs an inorder traversal of the BST, which results in elements being visited in sorted order.
'''

Traversal Algorithms:

• In-order, pre-order, and post-order traversal methods for visiting all nodes in a tree.