Course contentsShow
← Computer Science
Lesson 493 of 2,87212. Binary Search TreesFree lesson

What is a Binary Search Tree?

Define BST as a binary tree with ordering property: left subtree < node < right subtree.

What is a Binary Search Tree?

You'll learn: What makes a Binary Search Tree (BST) special and how its ordering property enables efficient searching.

The Core Idea

A Binary Search Tree is a binary tree with a crucial ordering rule: for every node, all values in its left subtree must be less than the node's value, and all values in its right subtree must be greater than the node's value.

This simple property transforms an ordinary binary tree into a powerful search structure.

The BST Property

Think of a BST like a decision tree for playing "higher or lower." At each node, you know exactly which direction to go:

  • Left subtree contains all smaller values
  • Node holds the current value
  • Right subtree contains all larger values

For example, imagine a node with value 50. All nodes in its left subtree (maybe 20, 35, 48) are less than 50. All nodes in its right subtree (maybe 60, 75, 90) are greater than 50. This pattern holds recursively for every node in the tree.

Why This Matters

Because of this ordering, you can search for a value by making a simple comparison at each node:

  • If the target is less than the current node, go left
  • If the target is greater, go right
  • If they're equal, you found it!

This eliminates roughly half the remaining possibilities with each comparison—much like binary search on a sorted array. That's why it's called a Binary Search Tree.

An Important Note

A BST is still a binary tree (each node has at most two children), but not every binary tree is a BST. The ordering property is what distinguishes it.

Key Takeaway: A Binary Search Tree maintains the ordering property where left subtree < node < right subtree at every level, enabling efficient search operations by eliminating half the tree with each comparison.