Binary Search Trees

Ordered trees that combine the speed of binary search with the flexibility of trees

You have met trees, and you have met binary search (halve the search each step). A binary search tree is what you get when you glue those two ideas together.
It is a tree with one tidy rule: at every node, everything smaller sits on its left, everything bigger sits on its right. Because of that rule, finding a number is a single walk down. Start at the top. Smaller than this node? Go left. Bigger? Go right. Keep going until you land on it. You never look at the other side of the tree. Try it below.

Each step throws away half of what is left, exactly like binary search, which is why finding, adding, or removing is fast: O(log n), as long as the tree stays reasonably balanced.
One more gift from the rule: if you read a search tree with an in-order walk (left, then node, then right, from the traversals lesson), the numbers come out perfectly sorted. That is not a coincidence; it falls straight out of "smaller on the left, bigger on the right".
The catch: if you insert numbers in an already-sorted order, the tree grows into one long lopsided line and the speed is gone. Real systems use self-balancing trees to keep that from happening.

BST search and insertpython

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

    def __init__(self): self.root = None

    def insert(self, val):
        def _insert(node, val):
            if not node: return self.Node(val)
            if val < node.val: node.left = _insert(node.left, val)
            elif val > node.val: node.right = _insert(node.right, val)
            return node
        self.root = _insert(self.root, val)

    def search(self, val):
        def _search(node, val):
            if not node: return False
            if val == node.val: return True
            return _search(node.left, val) if val < node.val else _search(node.right, val)
        return _search(self.root, val)

bst = BST()
for v in [5, 3, 7, 1, 4, 6, 8]:
    bst.insert(v)
print(bst.search(4))  # → True
print(bst.search(9))  # → False

🤔Quick Check

An in-order traversal of a BST gives you the values in what order?

Practice Exercises

0/1 solved

Exercise 1 of 1medium

⏱ 00:00

Validate BST

Determine if a binary tree is a valid BST.
Expected output: True

solution.py

1 / 1

Solve all 1 exercise to unlock completion

Previous Next