Binary Search Trees in Python: Insert, Search, and Three Traversal Orders

Fri Aug 14 2026

A binary search tree keeps every left subtree’s values smaller than its node and every right subtree’s values larger (or equal), which is what makes search and sorted traversal both possible on the same structure. This post builds a BST from scratch, inserts 8 values, then runs inorder/preorder traversals and several search calls against it.

The code

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


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

    def insert(self, value):
        # Smaller values go left, larger (or equal) go right, recursively,
        # until an empty spot is found.
        if self.root is None:
            self.root = TreeNode(value)
            return
        self._insert(self.root, value)

    def _insert(self, node, value):
        if value < node.value:
            if node.left is None:
                node.left = TreeNode(value)
            else:
                self._insert(node.left, value)
        else:
            if node.right is None:
                node.right = TreeNode(value)
            else:
                self._insert(node.right, value)

    def search(self, value):
        return self._search(self.root, value)

    def _search(self, node, value):
        if node is None:
            return False
        if node.value == value:
            return True
        if value < node.value:
            return self._search(node.left, value)
        return self._search(node.right, value)

    def inorder(self):
        # left, node, right -> visits values in sorted order for a BST
        result = []
        self._inorder(self.root, result)
        return result

    def _inorder(self, node, result):
        if node is None:
            return
        self._inorder(node.left, result)
        result.append(node.value)
        self._inorder(node.right, result)

    def preorder(self):
        # node, left, right
        result = []
        self._preorder(self.root, result)
        return result

    def _preorder(self, node, result):
        if node is None:
            return
        result.append(node.value)
        self._preorder(node.left, result)
        self._preorder(node.right, result)

    def height(self):
        return self._height(self.root)

    def _height(self, node):
        if node is None:
            return 0
        return 1 + max(self._height(node.left), self._height(node.right))


values = [50, 30, 70, 20, 40, 60, 80, 10]
tree = BST()
for v in values:
    tree.insert(v)

print("inserted:", values)
print("inorder (should be sorted):", tree.inorder())
print("preorder (insertion-shaped):", tree.preorder())
print("height:", tree.height())

for target in [40, 45, 80, 5]:
    print(f"search({target}) ->", tree.search(target))

8 values are inserted one at a time into an empty BST. inorder visits left-subtree, node, right-subtree recursively; preorder visits node, left-subtree, right-subtree. search walks left or right depending on the comparison at each node.

Running it

Real output:

inserted: [50, 30, 70, 20, 40, 60, 80, 10]
inorder (should be sorted): [10, 20, 30, 40, 50, 60, 70, 80]
preorder (insertion-shaped): [50, 30, 20, 10, 40, 70, 60, 80]
height: 4
search(40) -> True
search(45) -> False
search(80) -> True
search(5) -> False

inorder returned [10, 20, 30, 40, 50, 60, 70, 80] — fully sorted, from an insertion order that wasn’t sorted at all. preorder returned [50, 30, 20, 10, 40, 70, 60, 80], starting with 50 (the root, inserted first) rather than the smallest value. height came out to 4 for these 8 values. Of the four searches, search(40) and search(80) (both inserted values) returned True; search(45) and search(5) (never inserted) returned False.

Takeaway

Same 8 values, same tree: inorder produced sorted output while preorder reproduced the tree’s insertion-driven shape, and search correctly separated the two present values (40, 80) from the two absent ones (45, 5).