AlgoViz
HomeBinary Search Trees

Overview

Easy

The BST ordering property

In simple words

A binary search tree keeps smaller values on the left and bigger on the right, so searching is fast.

The idea

In a BST, every node's left subtree holds smaller keys and its right subtree holds larger keys. That invariant lets search, insert and delete run in O(height) — O(log n) when balanced.

5381479

Step 1 of 4. Search for 7. At each node go left if smaller, right if larger.

1/4
Optimal
timeO(h)spaceO(1)

Go left or right by comparison.

1function search(node, key) {2  while (node && node.val !== key)3    node = key < node.val ? node.left : node.right;4  return node;5}

Input

nodes
7, 6 edges

Output

found
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
search 7 in a BST rooted at 8 with left 3, right 10
Output:
go left from 10? no — 7 < 8, go left, then right from 3
Explanation:
Each comparison throws away a whole subtree, so a balanced tree of a million nodes needs about twenty steps.

Example 2

Input:
in-order walk of that tree
Output:
3, 7, 8, 10
Explanation:
Left, root, right always comes out sorted. That single fact answers most BST questions.

Finished the walkthrough? Add it to your streak.