Python Program to Implement Binary Search Tree

A Python program to implement a binary search tree uses a Node class with left and right children and an insert method to add values, like class Node: def __init__(self, key): self.left = None; self.right = None; self.val = key.

Examples

InputInsert values 10, 5, 15

OutputInorder traversal: 5 10 15

InputInsert values 20, 10, 30, 25, 35

OutputInorder traversal: 10 20 25 30 35

InputInsert single value 7

OutputInorder traversal: 7

How to Think About It

To build a binary search tree, start with an empty root. For each new value, compare it with the current node's value. If smaller, go left; if larger, go right. Insert the new value where there is no child node. This keeps the tree ordered for quick searching.

Algorithm

1

Create a node class with value, left child, and right child.

2

Start with an empty root node.

3

For each value to insert, compare it with the current node's value.

4

If value is less, move to the left child; if none, insert here.

5

If value is greater, move to the right child; if none, insert here.

6

Repeat until all values are inserted.

Code

python

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

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

    def inorder(self):
        elements = []
        if self.left:
            elements += self.left.inorder()
        elements.append(self.val)
        if self.right:
            elements += self.right.inorder()
        return elements

# Example usage
root = Node(10)
root.insert(5)
root.insert(15)
print("Inorder traversal:", *root.inorder())

Output

Inorder traversal: 5 10 15

Dry Run

Let's trace inserting 10, 5, 15 into the binary search tree and then do an inorder traversal.

1

Create root node

root.val = 10, root.left = None, root.right = None

2

Insert 5

5 < 10, root.left is None, so root.left = Node(5)

3

Insert 15

15 > 10, root.right is None, so root.right = Node(15)

4

Inorder traversal

Traverse left subtree (5), visit root (10), traverse right subtree (15)

Step	Action	Current Node	Left Child	Right Child
1	Create root	10	None	None
2	Insert 5	10	5	None
3	Insert 15	10	5	15
4	Inorder traversal	10	5	15

Why This Works

Step 1: Node structure

Each node stores a value and references to left and right children using self.left and self.right.

Step 2: Insert logic

To insert, compare the new value with the current node's value and decide to go left or right, creating a new node if the child is empty.

Step 3: Inorder traversal

Inorder traversal visits left subtree, then current node, then right subtree, which returns values in sorted order.

Alternative Approaches

Iterative insertion

python

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

def insert_iterative(root, key):
    current = root
    while True:
        if key < current.val:
            if current.left is None:
                current.left = Node(key)
                break
            else:
                current = current.left
        else:
            if current.right is None:
                current.right = Node(key)
                break
            else:
                current = current.right

root = Node(10)
insert_iterative(root, 5)
insert_iterative(root, 15)

# Inorder traversal same as before
print("Inorder traversal:", *root.inorder())

Uses a loop instead of recursion for insertion, which can be easier to understand for some but less elegant.

Using a class for BST

python

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

    def insert(self, key):
        if self.root is None:
            self.root = Node(key)
        else:
            self._insert(self.root, key)

    def _insert(self, node, key):
        if key < node.val:
            if node.left is None:
                node.left = Node(key)
            else:
                self._insert(node.left, key)
        else:
            if node.right is None:
                node.right = Node(key)
            else:
                self._insert(node.right, key)

    def inorder(self):
        return self._inorder(self.root) if self.root else []

    def _inorder(self, node):
        elements = []
        if node.left:
            elements += self._inorder(node.left)
        elements.append(node.val)
        if node.right:
            elements += self._inorder(node.right)
        return elements

bst = BST()
bst.insert(10)
bst.insert(5)
bst.insert(15)
print("Inorder traversal:", *bst.inorder())

Encapsulates the tree in a class for better structure and easier management of the root node.

Complexity: O(h) time, O(h) space

Time Complexity

Insertion and search take O(h) time, where h is the tree height. In the worst case (unbalanced), h can be n, making it O(n). In a balanced tree, h is log n.

Space Complexity

Space is O(h) due to recursion stack during insert or traversal. No extra data structures are used.

Which Approach is Fastest?

Iterative insertion avoids recursion overhead but both recursive and iterative have the same time complexity. Using a BST class improves code organization.

Approach	Time	Space	Best For
Recursive insertion	O(h)	O(h)	Simple code, easy to understand
Iterative insertion	O(h)	O(1)	Avoid recursion stack, better for deep trees
BST class encapsulation	O(h)	O(h)	Better structure and scalability