Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

root = {
    "value": 10,
    "left": {"value": 5, "left": None, "right": None},
    "right": {"value": 15, "left": None, "right": None},
}
print(root["value"], root["left"]["value"], root["right"]["value"])

A binary search tree uses ordering rules to decide where to go next

Tree traversals taught visit order. Binary search trees add a stronger structure rule: every decision to go left or right is based on value comparison. That makes search more directed than visiting every node blindly.

Core Explanation

In a binary search tree, smaller values go left and larger values go right.

This ordering property makes search more efficient than scanning an unordered collection in many cases.

Continuity from tree traversals

Traversal asked “which node should I visit next?” A BST adds another question: “based on the value, should I go left or right?”

Worked Example and Practice Lab

Expected output
10
6
14

This first example highlights the BST ordering idea: smaller values appear on the left side of the node, and larger values appear on the right side.

Expected output
4
14

Reading BST Decisions

These short examples focus on how comparisons guide the next step.

Compare against the root

A search starts by comparing the target value with the current node.

Follow a left decision

Values smaller than the current node move into the left subtree.

Follow a right decision

Values larger than the current node move into the right subtree.

Exercises

  1. Explain the BST ordering rule in your own words.

  2. Describe why 6 belongs on the left of 10 in the example.

  3. Give one reason BST structure can support faster search than an unordered collection.

  4. Explain how BST search differs from a traversal that visits every node.

Hint

At each node, ask one comparison question: is the target smaller, larger, or equal?

Guided Practice

All nodes are stored randomlyRandom placement would not support efficient search.
Left values are smaller and right values are larger than the nodeCorrect. That ordering rule is central to BSTs.
Every node has three childrenBST nodes do not require three children.
The tree stores only stringsBSTs can store ordered values of different kinds.

In the example values, which number would typically appear to the right of 10 in a BST?

66 is smaller than 10, so it would go left.
14Correct. 14 is larger than 10.
44 is smaller than 10.
88 is also smaller than 10.

Key Takeaway

Binary search trees turn value comparison into structure. That makes search more focused than generic traversal and prepares you for later graph-search notebooks where navigation strategy becomes even more important.

Programming for Machine Learning and Business
Tree Traversal Algorithms
Programming for Machine Learning and Business
Graph