Can a binary search tree have duplicate values?

It depends on the specific rules you are given. Most standard implementations do not allow duplicates. If they do, the duplicates must consistently be placed on one specific side (for example, always treating the left side as 'less than or equal to').

How do I print the values in numerical order?

You use a technique called an 'in-order traversal.' This is a recursive process where you visit the left child, then print the current node's value, and finally visit the right child. Because of the BST rule, this naturally prints the values from smallest to largest.

How do you delete a node?

Deleting a node is the trickiest part of a BST. If the node has no children, you just remove it. If it has one child, you replace the node with its child. If it has two children, you must find its 'in-order successor' (the smallest value in its right subtree), replace the node's value with the successor's value, and then delete the original successor.

What is a binary search tree?

A binary search tree (BST) is a hierarchical data structure made up of nodes, where each node has at most two children. The defining rule of a BST is that for any given node, all values in its left branch are smaller, and all values in its right branch are larger. Imagine playing a guessing game where I pick a number between 1 and 100. If you guess 50 and I say 'higher,' you instantly know the answer isn't 1 through 50. You just eliminated half the possibilities. A binary search tree organizes data in exactly this way, so every step down the tree cuts the remaining search space in half.

What it is: Nodes and pointers

In computer science, a tree is built out of 'nodes.' Each node contains a piece of data (like a number) and up to two connections, or pointers, to other nodes. We call these connections the 'left child' and the 'right child.' The very top node of the tree is called the 'root.' In a binary search tree, the strict rule is that every value in a node's left subtree must be less than the node's value, and every value in its right subtree must be greater.

Why it works: The power of halving

Because of how the data is sorted, you never have to look at every single node to find what you want. When you search for a value, you start at the root. If your target is smaller than the root, you move left. If it is larger, you move right. This means searching, inserting, and deleting can happen in $O(\log n)$ time, where $n$ is the number of nodes. It is vastly faster than scanning an entire list one by one.

Where students slip up: Unbalanced trees

A common trap is assuming a binary search tree is always perfectly balanced. If you insert numbers that are already sorted (like 1, 2, 3, 4, 5), each new number just gets added to the right of the previous one. Instead of a branching tree, you end up with a straight line. When this happens, the tree loses its halving power, and the time it takes to find a node drops to $O(n)$ , making it no faster than a basic linked list. This is why advanced trees (like AVL or Red-Black trees) have self-balancing rules.

Worked through

Insert the values 10, 5, 15, and 8 into an empty binary search tree.

First, we insert 10. Since the tree is empty, 10 becomes the root node. Next, we insert 5. We compare 5 to the root (10). Since 5 is less than 10, it becomes the left child of 10. Next, we insert 15. We compare 15 to the root (10). Since 15 is greater than 10, it becomes the right child of 10. Finally, we insert 8. We start at the root (10) and see that 8 is less than 10, so we move to the left child (5). We then compare 8 to 5. Since 8 is greater than 5, it becomes the right child of 5. The final tree has 10 at the top, 5 on the left, 15 on the right, and 8 branching to the right off of the 5.

Questions students ask

Ask about this topic

Explain at

Where this comes from: Introduction to Algorithms by Thomas H. Cormen et al. · Khan Academy: Computer Science Algorithms · OpenStax: Data Structures and Algorithms