Trees & BSTs

A tree is a hierarchy: one root node, each node with zero or more children, no cycles. A binary tree caps that at two children per node, usually called left and right.

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

root = Node(5)
root.left = Node(3)
root.right = Node(8)

A binary search tree adds one rule: for every node, everything in its left subtree is smaller, everything in its right subtree is larger (or equal, by convention). That rule is what makes search fast — at each node you eliminate an entire half of the remaining tree, the same idea as binary search on a sorted array.

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

If the tree stays roughly balanced, search/insert/delete are all O(log n). If you insert already-sorted data one at a time, it degenerates into a straight line — O(n). Self-balancing trees (AVL, red-black) fix that, at the cost of more bookkeeping on every insert.