The BST Rule: Smaller Left, Bigger Right

One simple rule

A binary search tree (BST) is a binary tree with one rule at every node:

• everything in the left subtree is smaller than the node,
• everything in the right subtree is bigger.

So searching is like binary search: at each node you know which half to throw away.

Think of it like this: The game “20 questions” with numbers: “Is it smaller than 50?” – one answer rules out a whole side.

class Node {
    int value;
    Node left, right;
    Node(int value) { this.value = value; }
}

public class Main {
    static Node insert(Node node, int v) {
        if (node == null) return new Node(v);
        if (v < node.value) node.left = insert(node.left, v);
        else if (v > node.value) node.right = insert(node.right, v);
        return node;                       // duplicates are ignored
    }

    static boolean contains(Node node, int v) {
        while (node != null) {
            if (v == node.value) return true;
            node = v < node.value ? node.left : node.right;   // go left or right
        }
        return false;
    }

    static void inorder(Node node, StringBuilder out) {
        if (node == null) return;
        inorder(node.left, out);
        out.append(node.value).append(' ');
        inorder(node.right, out);
    }

    public static void main(String[] args) {
        int[] values = {50, 30, 70, 20, 40, 60, 80};
        Node root = null;
        for (int v : values) root = insert(root, v);

        System.out.println(contains(root, 60) + " " + contains(root, 65));
        StringBuilder sb = new StringBuilder();
        inorder(root, sb);
        System.out.println("inorder: " + sb.toString().trim());
    }
}

Output

true false
inorder: 20 30 40 50 60 70 80

Inorder traversal of a BST always comes out sorted – left (smaller), node, right (bigger).

Smallest and biggest

The smallest value is found by going left until you can't; the biggest by going right. Each search, insert, min and max follows one path from the root down, so it costs O(height).

Remember: In a BST every operation walks one root-to-leaf path: O(height of the tree).