---
title: "Binary search tree in Python: the rule, O(h) operations and two interview problems"
url: https://algopath.pro/blog/binary-search-tree-python
language: en
summary: "Left smaller, right larger, for every node. The operation table, Python code, Validate BST with bounds, k-th smallest, lowest common ancestor in a BST and the mistakes."
updated: 2026-11-04
---

# Binary search tree in Python: the rule, O(h) operations and two interview problems

**Short answer.** A binary search tree has one rule. Left is smaller, right is larger. The rule holds for every node and its whole subtree. Search, insert and delete cost O(h), where h is the height. In a balanced tree that is O(log n). Below: the rule, Python code, two worked problems and the mistakes.

 

## What is a binary search tree?

 

Each node stores a value and two children. The whole left subtree is smaller than the node. The whole right subtree is larger. The condition must hold for every node, not just the root.

 

The rule lets a search follow one branch. Value smaller than the node: go left. Larger: go right. Each step discards a whole subtree.

 

Inorder traversal of such a tree yields values in ascending order. That is the most useful property in interviews.

 

## How does a binary search tree do its operations?

 

| Operation | How | Time |
| --- | --- | --- |
| Search | Walk down one branch | O(h) |
| Insert | Walk to an empty spot, add a leaf | O(h) |
| Minimum, maximum | Go all the way left or right | O(h) |
| Delete | Leaf: remove. One child: lift it. Two children: replace with the right subtree's minimum | O(h) |
| Sorted traversal | Inorder | O(n) |

 

The height h can be n in the worst case. Insert a sorted array in order and the tree becomes a chain. That is why libraries balance it.

 

## When does a problem need this pattern?

 

- "Given a binary search tree" in the statement.
- "Check whether the tree is a valid BST."
- "k-th smallest element", "closest value to x".
- "Lowest common ancestor of two nodes in a BST."

 

The statement says BST and your solution visits every node? You missed the rule. Almost always one branch is enough.

 

## What does one example look like?

 

Insert 8, 3, 10, 1, 6, 14 in that order. Root 8. 3 is smaller, left. 10 is larger, right. 1 is below 8 and below 3, leaf left of 3. 6 is below 8, above 3, right of 3. 14 goes right of 10.

 

Search for 6. Compare with 8, go left. Compare with 3, go right. Found in two steps. Inorder gives 1, 3, 6, 8, 10, 14.

 

## How do you write a binary search tree in Python?

 

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

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

def search(root, val):
    while root and root.val != val:
        root = root.left if val < root.val else root.right
    return root

def is_valid_bst(root, lo=float("-inf"), hi=float("inf")):
    if root is None:
        return True
    if not lo < root.val < hi:
        return False
    return is_valid_bst(root.left, lo, root.val) and \
           is_valid_bst(root.right, root.val, hi)

def kth_smallest(root, k):
    stack, node = [], root
    while stack or node:
        while node:
            stack.append(node); node = node.left
        node = stack.pop()
        k -= 1
        if k == 0:
            return node.val
        node = node.right
```

 

is_valid_bst passes bounds downward. Each node must sit strictly between them. That is the only correct check.

 

## How do you solve Validate Binary Search Tree?

 

The common mistake: compare a node only with its children. Take root 10 with left child 5, and give 5 a right child 12. That passes the check. But 12 sits in the left subtree of 10. That breaks the rule.

 

The right way: pass bounds. The left child's upper bound is the parent's value. The right child's lower bound is the same. Or run inorder and check it is strictly increasing.

 

## How do you find the lowest common ancestor in a BST?

 

In a general tree that is its own algorithm. In a BST one descent is enough. Both values below the node: go left. Both above: go right. Otherwise the node is the ancestor, the values split here.

 

Time O(h), memory O(1). A good example of the rule saving a whole traversal.

 

## What mistakes break a BST solution?

 

- Checking only direct children instead of passing bounds.
- Non-strict comparison on duplicates when the statement demands strict.
- Recursive insertion into a chain-shaped tree of a hundred thousand nodes.
- Visiting every node where one branch was enough.

 

## How do you explain a binary search tree in an interview?

 

State the rule: left smaller, right larger. For every node and its whole subtree. Say operations cost O(h), and h can be n. Mention balancing in one sentence.

 

Then show how the rule saves work in the actual problem. That is what gets tested.

 

Drill this pattern on the [binary search tree](/patterns/bst) page. Traversals live on the [tree traversal](/patterns/tree-traversal) page.

 

## FAQ

 

### How is a BST different from a heap?

 

In a heap the parent is smaller than both children, nothing more. A heap cannot search, but gives the minimum in O(1). A BST can search and iterate in order.

 

### What is a balanced tree?

 

A tree whose height stays near log n. AVL and red-black trees do that automatically on insert. Interviews ask for the idea, not the code.

 

### How do you delete a node with two children?

 

Find the minimum of the right subtree. Copy its value into the node. Delete that minimum, which has at most one child.

 

### Where do binary search trees show up in real systems?

 

Ordered maps: TreeMap in Java, std::map in C++. Database indexes use the wide version, the B-tree. Schedulers ordered by time.