Binary Search Trees (BST): The Ordering Property

A binary search tree (BST) is a binary tree with one extra rule, the BST property: for every node, all values in its left subtree are smaller and all values in its right subtree are larger. That single invariant turns a tree into a searchable structure where you can find, insert, or delete a value in O(h) time — O(log n) when the tree is balanced.

We reuse the standard TreeNode.

The BST property, precisely

For a node with value v:

• Every value in the left subtree is < v.
• Every value in the right subtree is > v.
• Both subtrees are themselves BSTs.

This must hold for every node, not just the root — a subtle point that trips people up.

            (8)
           /   \
        (3)     (10)
        /  \        \
     (1)   (6)      (14)
           /  \      /
        (4)   (7)  (13)

Searching is like binary search on an array: compare with the current node, then go left or right, halving the remaining tree each step.

Why in-order traversal gives sorted output

This is the BST’s signature property. An in-order traversal visits left, then node, then right. Because everything left of a node is smaller and everything right is larger, processing the node between its subtrees emits values in ascending order.

For the tree above, in-order yields: 1 3 4 6 7 8 10 13 14 — fully sorted.

void inorder(TreeNode* root, std::vector<int>& out) {
    if (root == nullptr) return;
    inorder(root->left, out);   // smaller values first
    out.push_back(root->val);   // then this node
    inorder(root->right, out);  // then larger values
}

void inorder(TreeNode root, List<Integer> out) {
    if (root == null) return;
    inorder(root.left, out);    // smaller values first
    out.add(root.val);          // then this node
    inorder(root.right, out);   // then larger values
}

function inorder(root, out = []) {
  if (root === null) return out;
  inorder(root.left, out);   // smaller values first
  out.push(root.val);        // then this node
  inorder(root.right, out);  // then larger values
  return out;
}

def inorder(root, out=None):
    if out is None:
        out = []
    if root is None:
        return out
    inorder(root.left, out)    # smaller values first
    out.append(root.val)       # then this node
    inorder(root.right, out)   # then larger values
    return out

For beginners: This gives a neat way to check whether a tree is a valid BST — run an in-order traversal and confirm the output is strictly increasing.

Validating a BST correctly

A common bug is checking only node.left.val < node.val < node.right.val locally. That misses violations deeper down. The robust approach passes a valid (low, high) range down the recursion:

bool isBST(TreeNode* node, long low, long high) {
    if (node == nullptr) return true;
    if (node->val <= low || node->val >= high) return false;
    return isBST(node->left, low, node->val) &&
           isBST(node->right, node->val, high);
}
// call: isBST(root, LONG_MIN, LONG_MAX)

boolean isBST(TreeNode node, long low, long high) {
    if (node == null) return true;
    if (node.val <= low || node.val >= high) return false;
    return isBST(node.left, low, node.val) &&
           isBST(node.right, node.val, high);
}
// call: isBST(root, Long.MIN_VALUE, Long.MAX_VALUE)

function isBST(node, low = -Infinity, high = Infinity) {
  if (node === null) return true;
  if (node.val <= low || node.val >= high) return false;
  return isBST(node.left, low, node.val) &&
         isBST(node.right, node.val, high);
}

def is_bst(node, low=float("-inf"), high=float("inf")):
    if node is None:
        return True
    if node.val <= low or node.val >= high:
        return False
    return is_bst(node.left, low, node.val) and \
           is_bst(node.right, node.val, high)

Both the in-order walk and the range check run in O(n) time and O(h) space.

Complexity & the balance caveat

The O(log n) promise only holds when the tree stays roughly balanced. Inserting already-sorted data into a plain BST produces a degenerate, linked-list-shaped tree with O(n) operations. The fix is self-balancing trees.

Going deeper: AVL and red-black trees restructure themselves on every insert/delete to guarantee O(log n) height no matter the input order.

Next steps

See the BST property in action with BST operations — search, insert, and delete — then keep it efficient with balanced trees & AVL.