Binary Search Trees

A tree is a connected, undirected graph with no cycles. Unlike a general graph, a tree has no loops — there is exactly one path between any two vertices.

A rooted tree is a tree in which one vertex is designated the root. This creates a hierarchy:

• The root has no parent
• Every other node has exactly one parent
• Nodes with no children are called leaves

A binary tree is a rooted tree in which every node has at most two children, referred to as the left child and right child.

A tree does not have to have a root — but a rooted tree does. A binary tree is always rooted.

The most practically important application of a binary tree is the binary search tree (BST). A BST is a binary tree with an ordering property that makes efficient searching possible:

BST ordering property: for every node, all values in its left subtree are less than the node's value, and all values in its right subtree are greater than the node's value.

This property holds at every node in the tree, not just at the root.

Inserting a sequence of values into a BST produces a tree whose structure depends on the order of insertion. Each new value is compared against existing nodes starting at the root and routed left or right until an empty position is found.

Worked example — insert in order: 5, 3, 7, 1, 4, 6, 8

Insert	Action
5	First value — becomes the root
3	3 < 5 → left child of 5
7	7 > 5 → right child of 5
1	1 < 5 → go left → 1 < 3 → left child of 3
4	4 < 5 → go left → 4 > 3 → right child of 3
6	6 > 5 → go right → 6 < 7 → left child of 7
8	8 > 5 → go right → 8 > 7 → right child of 7

Resulting BST:

        5
       / \
      3   7
     / \ / \
    1  4 6  8

The ordering property holds at every node: all values in the left subtree of 5 (1, 3, 4) are less than 5; all values in the right subtree (6, 7, 8) are greater. The same applies at each internal node.

Searching a BST uses the ordering property to eliminate half the remaining tree at each comparison — identical in logic to binary search on a sorted array.

Algorithm:

1. Start at the root
2. If the target equals the current node → found
3. If the target is less than the current node → move to left child
4. If the target is greater than the current node → move to right child
5. If the current node is null → target not in tree

Worked trace — search for 4 in the tree above:

Step	Current node	Compare with 4	Decision
1	5	4 < 5	Go left
2	3	4 > 3	Go right
3	4	4 = 4	Found

3 comparisons for a 7-node tree. For a balanced BST with $n$ nodes, the height is approximately ${\log }_{2}n$, giving a time complexity of $O(\log n)$.

Trace — search for 2 (not in tree):

Step	Current node	Compare with 2	Decision
1	5	2 < 5	Go left
2	3	2 < 3	Go left
3	1	2 > 1	Go right
4	null	—	Not found