Binary Search Trees

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

A Binary Search Tree (BST) satisfies one property: for every node, all values in its left subtree are smaller, and all values in its right subtree are larger.
This property enables O(log n) search, insert, and delete, *if the tree is balanced*.

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