BST Basics

The Idea

A binary search tree adds one rule to a binary tree: every value in a node's left subtree is smaller than it, and every value on the right is larger. The rule covers entire subtrees, not just direct children. Read the tree inorder and the values arrive sorted.

Real-World Example

A wine cellar racked by vintage. At every junction the older bottles go left and the newer ones right, all the way down the rows. Walk the aisle keeping left and you pass the years in strictly increasing order, having sorted nothing.

The Code

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

# BST rule: everything left of a node is smaller, everything right is larger
root = Node(50, Node(30, Node(20), Node(40)), Node(70, Node(60), Node(80)))

def inorder(n):
    return [] if not n else inorder(n.left) + [n.val] + inorder(n.right)

print(inorder(root))         # [20, 30, 40, 50, 60, 70, 80] -> sorted
print(root.left.right.val)   # 40: right of 30, yet still left of 50

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

t = Node(8, Node(3, None, Node(6)), Node(10))

def inorder(n):
  return [] if not n else inorder(n.left) + [n.val] + inorder(n.right)

print(inorder(t))