How to implement a Binary Search Tree (BST) in Python?

I’m trying to implement a Binary Search Tree in Python. I understand the concept of BSTs, but I’m having trouble with the implementation.

Could someone provide a simple yet comprehensive example of a BST in Python? The BST should have methods for insertion, search, and in-order traversal.

>Solution :

Sure, here’s a simple implementation of a Binary Search Tree in Python:

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

def insert(root, key):
    if root is None:
        return Node(key)
    else:
        if root.val < key:
            root.right = insert(root.right, key)
        else:
            root.left = insert(root.left, key)
    return root

def inorder(root):
    if root:
        inorder(root.left)
        print(root.val),
        inorder(root.right)

def search(root, key):
    if root is None or root.val == key:
        return root
    if root.val < key:
        return search(root.right, key)
    return search(root.left, key)

# Driver code
r = Node(50)
r = insert(r, 30)
r = insert(r, 20)
r = insert(r, 40)
r = insert(r, 70)
r = insert(r, 60)
r = insert(r, 80)

# Print in-order traversal of the BST
inorder(r)

This code first defines a Node class which will be used for individual nodes in the BST. The insert function is used to insert new nodes into the BST, the inorder function is used to print the BST in in-order traversal, and the search function is used to find a specific value in the BST.

Please note that this is a basic implementation and may need to be adjusted based on your specific use case.