Skip to content
Codextroop TechnologiesCodexLab

Trees & Binary Search Trees

A hierarchy with one rule that changes everything: smaller values left, larger values right. That rule turns searching into halving.

Class 11 to 12intermediate40 min2 lessons1 interactive lab
By the end you will be able to
  • Use the vocabulary: root, parent, child, leaf, height
  • Apply the binary search tree ordering rule to insert and search
  • Explain why an unbalanced tree degrades to O(n)

Finish first

Linked Lists

Cost at a glance

searchAverage
O(log n)
searchWorst
O(n)
insertAverage
O(log n)
Topic contents

Lesson 1 of 2

The ordering rule

A binary tree gives each node at most two children. A binary search tree adds the rule that makes it useful: everything in a node's left subtree is smaller than the node, and everything in its right subtree is larger.

That rule means every comparison is a decision that discards half the remaining tree. Searching 1,000 sorted values in a balanced BST takes about ten comparisons instead of a thousand. Step through a search in the visualizer and count the nodes it never even looks at. That is where the speed comes from.

Interactive lab

Binary search tree

Insert and search with the comparison at each node explained, and the traversal path highlighted.

Binary search tree

search / insert O(log n) average · O(n) worst
50307020406080
1 / 4

Start

Searching for 60, beginning at the root. Each comparison discards one whole subtree.

Continue

Lesson 2 of 2

When a tree stops being a tree

Insert 10, 20, 30, 40, 50 in that order and every value goes right. The result has the shape of a linked list, and search is back to O(n). The O(log n) promise depends entirely on the tree staying balanced, which is exactly why self-balancing variants such as AVL and red-black trees exist.

Continue

Worked examples

Read the code, then change it

Copy any example into the playground and break it on purpose. That is the fastest way to learn what each line is holding up.

BST searchJavaScript
function search(node, target) {
  if (!node) return false;
  if (node.value === target) return true;
  // One comparison discards half the remaining tree.
  return target < node.value
    ? search(node.left, target)
    : search(node.right, target);
}

Practice

Work these out yourself

No answer key here on purpose: these are the questions worth thinking through before you move on. Open one and work it out.

0/3 attempted

Assessment

Check your understanding

Answer each question, then read the explanation. That is where the learning is.

0/5
  1. Question 1: In a binary search tree, values smaller than a node live:
    Question 1 / 5

    In a binary search tree, values smaller than a node live:

    Select an option first
  2. Question 2: Average search cost in a balanced BST of n nodes:
    Question 2 / 5

    Average search cost in a balanced BST of n nodes:

    Select an option first
  3. Question 3: Inserting 10, 20, 30, 40 in ascending order into an empty BST produces:
    Question 3 / 5

    Inserting 10, 20, 30, 40 in ascending order into an empty BST produces:

    Select an option first
  4. Question 4: An in-order traversal of a binary search tree visits the values:
    Question 4 / 5

    An in-order traversal of a binary search tree visits the values:

    Select an option first
  5. Question 5: What do AVL and red-black trees add to a plain binary search tree?
    Question 5 / 5

    What do AVL and red-black trees add to a plain binary search tree?

    Select an option first
5 of 5 questions left.

Finished this topic?

0 of 2 lessons marked done. Marking the topic complete ticks the rest.