Binary Search Trees

A Binary Search Tree (BST) is a binary tree where every node follows one rule: all values in the left subtree are less than the node, and all values in the right subtree are greater.

This ordering property makes searching, insertion, and deletion efficient — on average O(log n) instead of O(n).

Key Terms:

• Root — The topmost node with no parent
• Node — An element storing a value, with up to two children
• Leaf — A node with no children
• Left Child — The child with a smaller value
• Right Child — The child with a greater value
• Height — The longest path from root to a leaf
• BST Property — left < parent < right for every node

The BST Property Illustrated

In the tree above, notice how every node satisfies the ordering rule. For example, the root 50 has 30 on its left (30 < 50) and 70 on its right (70 > 50). This pattern holds recursively at every level — making the entire tree a valid BST.

To insert a value into a BST, start at the root and compare. If the value is less, go left. If greater, go right. Repeat until you find an empty spot — that is where the new node goes.

Enter a number below and watch it traverse down the tree to its correct position.

There are three classic ways to visit every node in a BST:

• In-Order (Left, Root, Right) — Visits nodes in sorted order
• Pre-Order (Root, Left, Right) — Root is visited first
• Post-Order (Left, Right, Root) — Root is visited last

Click a traversal button to animate the visit order on the tree below.

Searching a BST is fast because you eliminate half the tree at each step. Compare the target to the current node: go left if smaller, right if larger. This gives O(log n) average time vs O(n) for an unsorted array.

Enter a value and watch the search path animate from the root.

Deleting from a BST has three cases:

1. Leaf node — Simply remove it. No children to worry about.
2. One child — Replace the node with its only child.
3. Two children — Replace with its in-order successor (smallest value in the right subtree), then delete the successor.

Click on a node in the tree to select it, then click Delete to see which case applies and watch the deletion animate.

1. What is the average time complexity of searching for a value in a balanced BST?

2. In an in-order traversal of a BST, the values are visited in which order?

3. When deleting a node with two children from a BST, it is replaced by its: