---
title: "Trees and Binary Search Trees"
description: "A structure of nodes with one root and no cycles, and the binary search tree rule that keeps smaller values left and larger values right. Walking the tree left, node, right returns the values in sorte"
canonical: https://lightmysky.com/learn/computing/trees-and-binary-search-trees-mt_7PGHiAY54b
source: https://lightmysky.com/learn/computing/trees-and-binary-search-trees-mt_7PGHiAY54b.md
retrieved: 2026-09-12
---

> **Agent view.** This is the Markdown twin of the page, for tools and assistants.
> When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md
> API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md
> Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt
> Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json
> Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`.

# Trees and Binary Search Trees

A structure of nodes with one root and no cycles, and the binary search tree rule that keeps smaller values left and larger values right. Walking the tree left, node, right returns the values in sorted order.

Subject: Computing · Area: Algorithms & Data Structures · Ages 17 to 18
Page: https://lightmysky.com/learn/computing/trees-and-binary-search-trees-mt_7PGHiAY54b

## Ready when they can

- Insert a run of values into an empty binary search tree and draw the result
- Search for a value and count the comparisons against the tree's height
- Walk a tree in order and show that the output comes out sorted

## Lesson: Trees that keep values sorted

A tree is nodes with one root and no cycles, where each node holds a value and links to children. In a binary search tree every node has at most two children, with smaller values left and larger values right. The first value you insert into an empty tree becomes the root.

**Example.** Insert 5, 2, 8, 1, 3 in that order and watch the rule work. 5 becomes the root, 2 goes left, 8 goes right, 1 goes left of 2, and 3 goes left of 5 then right of 2. So 3 lands as the right child of 2.

You search by comparing at each node and counting one comparison per visit. Finding 3 visits 5, then 2, then 3, which is 3 comparisons. Sorted arrivals are the trap: inserting 1 through 7 in order chains every node right, and searching that chain costs like a linked list instead of a short bushy tree.

**Tip.** You check any tree with an in order walk: left subtree, then the node, then the right subtree. For the example tree that prints 1, 2, 3, 5, 8, sorted smallest to largest. If your walk is unsorted, one value sits on the wrong side.

**Recap.** Smaller left and larger right keeps order, and an in order walk prints values sorted.

## Practice

12 questions on this page, each with its working shown.

## Needs first

- [Linked Lists and Nodes That Point](https://lightmysky.com/learn/computing/linked-lists-and-nodes-that-point-mt_HvY7_-M2Zj)
- [Merge Sort and Divide and Conquer](https://lightmysky.com/learn/computing/merge-sort-and-divide-and-conquer-mt_OAutL4c7_l)

## Opens up

- [Lexing and Parsing: From Text to a Syntax Tree](https://lightmysky.com/learn/computing/lexing-and-parsing-from-text-to-a-syntax-tree-mt_-ZlCxZ3SOh)
- [Indexes: B-Trees and the Cost of a Lookup](https://lightmysky.com/learn/computing/indexes-b-trees-and-the-cost-of-a-lookup-mt_1Z5EQTqooI)
- [Graphs and How to Store Them](https://lightmysky.com/learn/computing/graphs-and-how-to-store-them-mt_tSO-F1sTuu)
- [Heaps and Priority Queues](https://lightmysky.com/learn/computing/heaps-and-priority-queues-mt_W-ofiMiXWs)
- [Decision Trees and Ensembles](https://lightmysky.com/learn/computing/decision-trees-and-ensembles-mt_xo9EEd4R1i)