A binary search tree promises that every value in a node's left subtree is smaller than the node, and every value in its right subtree is larger. Checking each node against only its own two children is not enough. Two checks keep all of it: pass an allowed range down the tree, or read the values back in order. Both visit each node once.
Start at the root with the range (−∞, +∞). Going left, the parent's value becomes the new upper bound. Going right, it becomes the new lower bound. A node is legal only if it fits the range it inherits. The right pane runs the tempting shortcut that only compares a node to its children. Load the trap and watch the two disagree. Click any node to change its value, or a dashed + to add one.
How to read this: Each circle is a value in the tree. The small text under a checked node is the range it must fall inside: (4, 8) means bigger than 4 and smaller than 8, and ∞ means no limit on that side. A square bracket means equal is allowed.
Try this: With Trap loaded, press Run and watch the right pane say valid while the left pane catches 9.
Each call hands its children a narrower window. The window carries every ancestor's limit at once, so a node five levels down is checked against all five ancestors with just two comparisons.
The naive check looks right on every small example you try by hand. It fails when a node fits its parent but sits on the wrong side of a grandparent or older ancestor.
An in-order walk visits the left subtree, then the node, then the right subtree. On a binary search tree that walk reads the values in sorted order. So walk it, remember only the previous value, and stop at the first value that fails to go up.
How to read this: The walk reads values left to right across the tree; the row below shows them in the order read. In a valid tree they only go up.
Try this: Step through Trap and watch for the first red ≥ in the row.
If the in-order sequence is strictly increasing, every node is larger than everything printed before it and smaller than everything printed after it. That is exactly the BST rule, so one pass with one variable decides it. The stack holds one frame per level, the same mechanism that solves the Tower of Hanoi in 005 · Recursion & fractals.
Build a tree by inserting values one at a time: compare with the root, go left if smaller and right if larger, and drop the value into the first empty spot. Every result is a valid BST, but the shape depends on the order. A search costs one comparison per level it passes, so the height is the worst-case search cost.
How to read this: Values from the row below drop into the tree one by one: smaller goes left, larger goes right. Taller trees mean slower searches.
Try this: Press Sorted and watch the tree turn into a long diagonal chain.
Sorted input sends each new value right of everything already there, so the tree becomes a chain with one node per level: a linked list that costs n comparisons to search. A good order keeps the height near ⌈log₂(n+1)⌉. A random order gives O(log n) height on average. Self-balancing trees such as AVL and red-black trees rotate nodes after inserts to guarantee O(log n) height whatever the order.