Binary Search Tree Basics: The Ordering Rule Explained

A binary search tree is a binary tree with one extra rule, and almost everything useful about it follows from reading that rule carefully. Smaller values go left and larger values go right, not just at the top, not just for direct children, but for entire subtrees, all the way down. Get that sentence right and the minimum, the maximum, sorted order, the next larger value and range queries all fall out without any extra machinery.

The problem it solves

You want a collection that stays in order while it changes. A sorted array keeps order but pays for every insert by shifting elements. A hash set inserts in constant time on average but has no order at all: it cannot say which value comes next after 41, or how many values lie between 100 and 120.

A BST keeps the order in the shape of the tree itself. The walks that insert and look up a key are covered in BST insert and search; this article is about what the ordering rule gives you once the tree exists.

The intuition

The rule. For every node, every value in its left subtree is smaller and every value in its right subtree is larger. In the lesson's tree, 40 is the right child of 30, so it must be larger than 30. It also sits inside 50's left subtree, so it must be smaller than 50. Each node therefore lives inside an interval set by all of its ancestors, not just its parent; checking only parent and child is the classic mistake that validating a BST is about.

Four consequences:

• Inorder is sorted. An inorder walk visits the left subtree, then the node, then the right subtree. Everything on the left is smaller and everything on the right larger, so values come out in increasing order; the traversal article covers the walk itself.
• Min and max are at the ends. Keep going left until you cannot: nothing smaller exists. The maximum is the rightmost node.
• The successor is one walk. The smallest value greater than x: whenever a node is larger than x, remember it and go left to look for a smaller candidate; otherwise go right.
• Whole subtrees can be skipped. To count values in [lo, hi], a node below lo rules out its entire left subtree, and a node above hi its entire right subtree.

All of these cost one step per level, so the height decides everything. Built from sorted data by repeatedly taking the middle value as the root, a tree of n values is as short as possible, about log2(n) levels. Built by inserting sorted data one value at a time, it degenerates into a chain, which types of binary trees describes.

Duplicates need a policy decided up front: reject them, keep a count on the node, or always send equal values to the same side.

Watch it run

The animation uses the lesson's seven-node tree, rooted at 50. A BST adds one rule to a binary tree, and the rule is about whole subtrees, not direct children. Everything in 50's left subtree is smaller: 30, 20 and 40 are all below 50. Everything on the right is larger: 70, 60 and 80 all beat 50. Then watch 40: it sits to the right of 30, yet it is still left of 50, and 30 is less than 40 is less than 50 holds. The inorder walk begins: keep going left while you can, and where you stop is the smallest value, 20. Then left, node, right, so smaller values always arrive first, and the strip fills in 30, 40, 50, 60, 70, 80. The last frame shows the list sorted, and nothing was ever sorted.

The code

The lesson's tree, an inorder walk, and the two ends. The leftmost value of 50's right subtree is the smallest value larger than 50:

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

root = Node(50, Node(30, Node(20), Node(40)), Node(70, Node(60), Node(80)))

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

def leftmost(node):
    while node.left:                       # nothing smaller exists once left runs out
        node = node.left
    return node.val

def rightmost(node):
    while node.right:
        node = node.right
    return node.val

print(inorder(root))                       # [20, 30, 40, 50, 60, 70, 80]
print(leftmost(root), rightmost(root))     # 20 80
print(leftmost(root.right))                # 60 -- the smallest value larger than 50

A balanced tree built from sorted data, the successor walk, and a range count that records every node it visits:

def from_sorted(vals):
    """The middle value becomes the root, so both sides get half: height ~ log2(n)."""
    if not vals:
        return None
    mid = len(vals) // 2
    return Node(vals[mid], from_sorted(vals[:mid]), from_sorted(vals[mid + 1:]))

def height(node):
    return 1 + max(height(node.left), height(node.right)) if node else 0

def successor(node, x):
    """Smallest value strictly greater than x, in one walk from the root."""
    best = None
    while node:
        if node.val > x:
            best, node = node.val, node.left   # a candidate; look for a smaller one
        else:
            node = node.right                  # too small: everything left is too
    return best

def count_range(node, lo, hi, visited):
    """How many values fall in [lo, hi], skipping subtrees the rule rules out."""
    if not node:
        return 0
    visited.append(node.val)
    if node.val < lo:
        return count_range(node.right, lo, hi, visited)   # whole left side is below lo
    if node.val > hi:
        return count_range(node.left, lo, hi, visited)    # whole right side is above hi
    return 1 + count_range(node.left, lo, hi, visited) + count_range(node.right, lo, hi, visited)

big = from_sorted(list(range(0, 2000, 2)))           # 1,000 even numbers
seen = []
print(height(big), successor(big, 41), successor(big, 1998))   # 10 42 None
print(count_range(big, 100, 120, seen), len(seen))             # 11 19

A thousand values fit in 10 levels. Counting the 11 values between 100 and 120 touched 19 nodes out of 1,000; every other subtree was ruled out by a single comparison. Then a check on 1,000 seeded random sets: inorder must equal the sorted input, the height must be the minimum possible, n.bit_length() levels, and the ends, the successor of every probe and every range count must match a brute force with bisect and a plain filter:

import random
from bisect import bisect_right

rng = random.Random(34)
ok = True
for _ in range(1000):
    vals = sorted(rng.sample(range(500), rng.randint(0, 60)))
    tree = from_sorted(vals)
    ok &= inorder(tree) == vals
    ok &= height(tree) == len(vals).bit_length()          # ceil(log2(n + 1)) levels
    if vals:
        ok &= (leftmost(tree), rightmost(tree)) == (vals[0], vals[-1])
    for x in range(-1, 501, 7):
        i = bisect_right(vals, x)
        ok &= successor(tree, x) == (vals[i] if i < len(vals) else None)
    lo = rng.randint(0, 499)
    hi = rng.randint(lo, 499)
    ok &= count_range(tree, lo, hi, []) == sum(lo <= v <= hi for v in vals)
print(ok)                                                 # True

The complexity

• Min, max, successor: O(h), one step per level.
• Range count: O(h + k) for k values in range, since only nodes on the two boundary paths and inside the range are visited.
• Inorder listing: O(n).
• Height: about log2(n) when balanced, up to n for a chain. The Big-O cheat sheet lists both cases.

Where it goes wrong

• Checking only the parent. 45 as the right child of 40 under the lesson's 30 is fine; 55 there is not, because it would sit in 50's left subtree.
• Assuming O(log n). Only a balanced tree guarantees it.
• No duplicate rule. Equal values sent both ways break search and counting.
• Recursing on a chain. A degenerate tree thousands deep exceeds Python's recursion limit; walk it with a loop.

When it shows up in interviews

As the foundation for a family of questions: kth smallest via inorder, inorder successor, range sum of a BST, convert a sorted array to a balanced BST, and the lowest common ancestor in a BST. Interviewers listen for "whole subtree" and for height, not log n, as the cost.

How to say it in an interview

"A BST orders whole subtrees: everything left of a node is smaller and everything right is larger, so each node lives inside an interval set by its ancestors. That makes inorder traversal sorted, puts the minimum at the leftmost node and the maximum at the rightmost, and lets a successor or range query discard a whole subtree per comparison. Everything costs O(h), so I keep the tree balanced, for example by building it from sorted data with the middle element as the root, and I choose a duplicate policy up front."