Binary Trees: BST, Traversals & Balanced Trees Explained

A binary tree is a hierarchy in which each node has at most two children, called the left and right child. A binary search tree (BST) adds one ordering rule — every value in a node's left subtree is smaller than the node, and every value in its right subtree is larger — and that single rule is what makes searching fast.

The headline numbers: on a balanced BST, search, insert, and delete all run in $O(\log n)$ time, because the tree's height stays close to $\log_2 n$. On an unbalanced tree, the same operations can degrade to $O(n)$.

Binary tree vs binary search tree

Every BST is a binary tree, but not every binary tree is a BST. The BST property must hold at every node:

Note the wording: the rule applies to the entire subtree, not just the immediate children. A tree can have every parent–child pair correctly ordered and still violate the BST property deeper down — this is the classic trap in BST validation problems.

The four traversals

A traversal is a systematic way to visit every node exactly once. Three are depth-first and differ only in when the node itself is visited; the fourth is breadth-first.

Worked example: four traversals of one tree

Use this BST:

        8
       / \
      3   10
     / \    \
    1   6    14

Walking each traversal by hand:

The inorder result comes out sorted. That is not a coincidence — inorder traversal of any valid BST always produces the keys in ascending order, which makes it a quick correctness check.

Worked example: search and insert in a BST

Search for $6$ in the tree above. Start at the root:

1. At $8$: since $6 < 8$, go left.
2. At $3$: since $6 > 3$, go right.
3. At $6$: found, after $3$ comparisons.

A linear scan of the same six values could need up to $6$ checks; the BST needed $3$ because each comparison discarded an entire subtree.

Insert $7$: follow the same path — $8 \to 3 \to 6$ — then since $7 > 6$ and $6$ has no right child, attach $7$ as the right child of $6$. Insertion is just a failed search plus one link.

Why balance matters

Every BST operation walks one root-to-leaf path, so the cost is $O(h)$ where $h$ is the height. Balance determines $h$:

The worst case is easy to trigger: insert already-sorted data $1, 2, 3, 4, 5$ into an empty BST and every node gets only a right child. The "tree" is now a linked list.

Self-balancing trees — AVL trees and red-black trees — fix this by performing local rotations after inserts and deletes, guaranteeing $h = O(\log n)$ no matter the input order. This is why standard library structures like C++ std::map and Java TreeMap are built on red-black trees.

Common mistakes

Validating a BST by checking only the children

Comparing each node to its immediate children misses violations deeper in the subtree. Correct validation passes a valid $(\min, \max)$ range down the recursion.

Assuming $O(\log n)$ without balance

The logarithmic bound is a property of balanced trees, not of BSTs in general. Sorted input on a plain BST gives $O(n)$ behavior.

Expecting sorted output from any binary tree

Inorder traversal yields ascending order only when the BST property holds. On an arbitrary binary tree, inorder output is just one particular visiting sequence.

Ignoring the duplicates policy

Decide up front whether duplicates go left, go right, or are stored with a count. Mixing conventions in one tree breaks both search and the sorted-inorder guarantee.

Build one yourself

Insert $5, 2, 8, 1, 3$ into an empty BST and draw the result, then write out all four traversals by hand. Afterwards, insert $1, 2, 3, 4, 5$ in that order into a fresh tree and compare the shapes — seeing the degenerate chain appear once is worth more than rereading the definition.