AI Hints
Home›DSA in Python Tutorial›Measuring and Searching Trees
DSA in Python · Lesson 65 of 132

Binary Search Trees

Smaller left, bigger right.

⏱ 2 min read▶ Video at 1:16:30🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

A binary search tree follows one rule. Everything in a node's left subtree is smaller than it, and everything in its right subtree is bigger. That rule turns a tree into something you can search like binary search.

Binary Search Trees
From the video: Binary Search Trees
  • One rule
  • Smaller on the left
  • Bigger on the right

Searching a BST

Our sample tree is a binary search tree. To find a value, start at the root. If the target is smaller, go left. If it's bigger, go right. Each step throws away a whole subtree. We print the path. Run it. Finding thirteen takes just four steps.

bst_search.pypython
from tree import sample

def search(node, target):
    path = []
    while node:
        path.append(node.value)
        if target == node.value:
            return path
        node = node.left if target < node.value else node.right
    return path + ["not found"]

print(search(sample(), 13))
print(search(sample(), 5))
Output
[8, 10, 14, 13]
[8, 3, 6, 4, 'not found']
Also uses tree.py
class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value, self.left, self.right = value, left, right

def sample():
    return TreeNode(8,
        TreeNode(3, TreeNode(1), TreeNode(6, TreeNode(4), TreeNode(7))),
        TreeNode(10, None, TreeNode(14, TreeNode(13))))

PICTURE = '        8\n      /   \\\n     3     10\n    / \\      \\\n   1   6      14\n      / \\    /\n     4   7  13'

BST costs

In a balanced binary search tree, searching, inserting, and deleting are all O of log N, because each step halves what's left. And an in order traversal lists every value in sorted order. That's why databases and sorted maps are built on trees like this.

keyvalue
SearchO(log n) when balanced
InsertO(log n) when balanced
In ordersorted output
Used indatabases, sorted maps

Summary

In a binary search tree, smaller values go left, and bigger values go right. Searching follows one path down. Next, building one by inserting values.

Key takeaways
  • Left < node < right
  • Follow one path
  • O(log n) when balanced
Next up: Inserting into a BST — finding the right spot