How it works
The ordering property constrains entire subtrees, not merely immediate children. That is what lets search discard half the tree at each step.
Verify the property recursively when checking whether a tree is a valid BST.
Common error
Checking only parent against children, which accepts trees that are not valid search trees.
Worked example
Java snippets run inside a main method. Add import java.util.*; when collection types are used.
Java
TreeSet<Integer> keys = new TreeSet<Integer>();
for (int k : new int[]{8,4,12,2,6}) keys.add(k);
System.out.println(keys);Output
[2, 4, 6, 8, 12]For a strict unique-key binary search tree, smaller keys belong in the left subtree and larger keys in the right subtree. The sorted output of TreeSet illustrates ordered-set behavior; its implementation also maintains balance.
Exercises
6.3.1 · Explain
In a BST rooted at 8 with left child 4 and right child 12, where is a new key 10 inserted?
Show solution
Compare with 8 and go right, then compare with 12 and go left. It becomes the left child of 12 if that position is empty.
6.3.2 · Explain
When removing a BST node with two children, what key can replace it while preserving sorted order?
Show solution
Use its inorder successor, the smallest key in the right subtree, or its inorder predecessor. Then correctly remove or relink that replacement node.