BST rule

Left child smaller, right child larger in a BST.

BST property

A binary search tree (BST) is a binary tree where all values in a node's left subtree are smaller than the node's value, and all values in the right subtree are larger.

Thanks to this rule, search, insert and delete are O(log n) (when balanced). Inorder traversal gives increasing order.

The BST is a fundamental structure for fast search on sorted data. If unbalanced it degrades to O(n).

BST property

The BST rule is recursive: every subtree is also a BST. All values in the left subtree are smaller than the root, all in the right subtree are larger.

This applies binary-search logic to searching: if the target is smaller than the root go left, if larger go right. Each step halves the search space.

A balanced BST has height log n; each search takes at most that many steps.

Exercise Check BST

Write is_bst(node, lo, hi). Recursively check node value is in (lo, hi). Print True with root = Node(5); root.left = Node(3); print(is_bst(root, -9999, 9999)).

Show example solution

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
def is_bst(node, lo, hi):
    # Check BST
    if node is None:
        return True
    if not (lo < node.val < hi):
        return False
    return is_bst(node.left, lo, node.val) and is_bst(node.right, node.val, hi)
root = Node(5)
root.left = Node(3)
print(is_bst(root, -9999, 9999))

Test yourself

What are left subtree values in a BST?
- Larger than the node
- Smaller than the node
- Equal
- Random
Show answer

Smaller than the node — Smaller than the node

Search direction

if target ____node.val: go left

Show answer

if target <node.val: go left

BST rule: match the terms

Left subtree

Smaller
Right subtree

Larger
Inorder

Increasing
Balanced

O(log n)

Next lesson: BST insert

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies