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

BST Search: Finding a Node

Learn how to search for a value in a BST by comparing keys and traversing left or right subtrees recursively.

BST Search: Finding a Node

What you'll learn: How to efficiently find a value in a Binary Search Tree by exploiting its ordering property.

The Core Idea

Searching in a BST is like playing a guided guessing game. Because of the BST invariant (left subtree < node < right subtree), at each node you can eliminate half the remaining tree by comparing your target value with the current node's key.

Start at the root. If your target matches the current node's value, you're done! If your target is smaller, it must be in the left subtree (if it exists at all). If your target is larger, it must be in the right subtree. Repeat this process, moving left or right, until you either find the value or reach a null child (meaning the value isn't in the tree).

How It Works

  1. Compare your search value with the current node
  2. Match? Return the node (found!)
  3. Smaller? Recursively search the left subtree
  4. Larger? Recursively search the right subtree
  5. Hit null? The value doesn't exist in the tree

Why This Is Powerful

Unlike searching an unsorted binary tree (which requires checking every node), BST search has average-case O(log n) time complexity in balanced trees. Each comparison cuts the search space in half, similar to binary search on a sorted array.

Think of it like looking up a word in a dictionary: you don't start at page 1 and flip through every page. You open somewhere in the middle, see if your word comes before or after, and eliminate half the dictionary with each check.

Key Takeaway: BST search leverages the ordering invariant to traverse left or right at each step, achieving efficient O(log n) average-case search by eliminating half the tree with each comparison.