Describe how you would implement a binary search tree in Python. Write a simple code example.

Python Data Structures - Interview Questions and Answers

To implement a binary search tree (BST) in Python, I start by defining a Node class to represent each element in the tree, with attributes for the data, left child, and right child. Then, I create a BinarySearchTree class to handle insertion and traversal.

Here’s a basic example:

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

class BinarySearchTree:
    def __init__(self):
        self.root = None

    def insert(self, data):
        if self.root is None:
            self.root = Node(data)
        else:
            self._insert_recursive(self.root, data)

    def _insert_recursive(self, node, data):
        if data < node.data:
            if node.left is None:
                node.left = Node(data)
            else:
                self._insert_recursive(node.left, data)
        else:
            if node.right is None:
                node.right = Node(data)
            else:
                self._insert_recursive(node.right, data)?

This code provides a starting point for a BST with insertion functionality. Each insertion checks if the data should go to the left or right subtree and places it accordingly, ensuring the BST’s properties are maintained.