Tree Search Algorithm Overview

👋 Welcome Gophers! In this lesson, we are going to be covering Tree Search algorithms, specifically working with Binary Search Trees (BSTs).

Overview

While binary search on arrays is fantastic, Binary Search Trees take that idea and make it dynamic. Instead of needing to keep an array sorted, a BST maintains search properties through its structure.

A Binary Search Tree is a tree where for every node:

All values in the left subtree are smaller
All values in the right subtree are larger

This structure lets us search, insert, and delete efficiently—usually in logarithmic time!

BST Properties

The magic of BSTs comes from their organization:

Left child < parent < right child: This property is maintained at every node
Ordered structure: An in-order traversal gives you sorted data
Efficient searching: The structure guides your search path

How BST Search Works

Searching a BST is elegant:

Start at the root
Compare target with current node
If equal, found it!
If target is smaller, go left
If target is larger, go right
Repeat until found or you reach a leaf with no valid direction

It’s like binary search, but the data structure guides you along the way!

Time Complexity: The Catch

Average case: O(log n) when the tree is balanced
Worst case: O(n) when the tree becomes a linked list (unbalanced)

The worst case happens when you insert sorted data into a BST—it creates a lopsided tree. This is why self-balancing trees (AVL trees, Red-Black trees) exist, but we’ll focus on basics here.

Insertion

To maintain BST properties when inserting:

Start at root
If new value is smaller, go left; if larger, go right
When you find an empty spot, insert the new node

This maintains the BST ordering property automatically.

Visual Example

Here’s a Binary Search Tree with a search path highlighted:

<svg viewBox="0 0 700 420" xmlns="http://www.w3.org/2000/svg">
  <!-- Background -->
  <rect width="700" height="420" fill="#1a1a2e"/>

  <!-- Title -->
  <text x="350" y="30" text-anchor="middle" fill="#00d9ff" font-size="18" font-weight="bold">
    Binary Search Tree: Searching for 35
  </text>

  <!-- Root node -->
  <circle cx="350" cy="80" r="22" fill="#ff6b6b" stroke="#00d9ff" stroke-width="2"/>
  <text x="350" y="87" text-anchor="middle" fill="#fff" font-size="14" font-weight="bold">50</text>

  <!-- Lines to children -->
  <line x1="335" y1="100" x2="250" y2="140" stroke="#666" stroke-width="2"/>
  <line x1="365" y1="100" x2="450" y2="140" stroke="#666" stroke-width="2"/>

  <!-- Left subtree root -->
  <circle cx="250" cy="160" r="22" fill="#4ecdc4" stroke="#00d9ff" stroke-width="2"/>
  <text x="250" y="167" text-anchor="middle" fill="#fff" font-size="14" font-weight="bold">30</text>

  <!-- Right subtree root -->
  <circle cx="450" cy="160" r="22" fill="#4ecdc4" stroke="#00d9ff" stroke-width="2"/>
  <text x="450" y="167" text-anchor="middle" fill="#fff" font-size="14" font-weight="bold">70</text>

  <!-- Lines from 30 -->
  <line x1="235" y1="180" x2="180" y2="220" stroke="#666" stroke-width="2"/>
  <line x1="265" y1="180" x2="320" y2="220" stroke="#666" stroke-width="2"/>

  <!-- 30's children -->
  <circle cx="180" cy="240" r="22" fill="#4ecdc4" stroke="#00d9ff" stroke-width="2"/>
  <text x="180" y="247" text-anchor="middle" fill="#fff" font-size="14" font-weight="bold">20</text>

  <circle cx="320" cy="240" r="22" fill="#45b7aa" stroke="#ff6b6b" stroke-width="3"/>
  <text x="320" y="247" text-anchor="middle" fill="#fff" font-size="14" font-weight="bold">40</text>

  <!-- Lines from 70 -->
  <line x1="435" y1="180" x2="380" y2="220" stroke="#666" stroke-width="2"/>
  <line x1="465" y1="180" x2="520" y2="220" stroke="#666" stroke-width="2"/>

  <!-- 70's children -->
  <circle cx="380" cy="240" r="22" fill="#4ecdc4" stroke="#00d9ff" stroke-width="2"/>
  <text x="380" y="247" text-anchor="middle" fill="#fff" font-size="14" font-weight="bold">60</text>

  <circle cx="520" cy="240" r="22" fill="#4ecdc4" stroke="#00d9ff" stroke-width="2"/>
  <text x="520" y="247" text-anchor="middle" fill="#fff" font-size="14" font-weight="bold">80</text>

  <!-- Lines from 40 -->
  <line x1="305" y1="260" x2="280" y2="300" stroke="#666" stroke-width="2"/>
  <line x1="335" y1="260" x2="360" y2="300" stroke="#666" stroke-width="2"/>

  <!-- 40's children -->
  <circle cx="280" cy="320" r="22" fill="#95e1d3" stroke="#00d9ff" stroke-width="2"/>
  <text x="280" y="327" text-anchor="middle" fill="#fff" font-size="14" font-weight="bold">35</text>

  <circle cx="360" cy="320" r="22" fill="#4ecdc4" stroke="#00d9ff" stroke-width="2"/>
  <text x="360" y="327" text-anchor="middle" fill="#fff" font-size="14" font-weight="bold">45</text>

  <!-- Search path highlighting -->
  <text x="50" y="380" fill="#00d9ff" font-size="13" font-weight="bold">Search Path for 35:</text>
  <text x="50" y="405" fill="#a8dadc" font-size="12">50 (target 35 &lt; 50, go left) → 30 (target 35 &gt; 30, go right) → 40 (target 35 &lt; 40, go left) → 35 (Found!)</text>

  <text x="550" y="380" fill="#888" font-size="11">Red outline = Current</text>
  <text x="550" y="400" fill="#888" font-size="11">Light = Found target</text>
</svg>

Notice how the tree structure guides our search: we follow the comparison rules at each step, never exploring irrelevant subtrees.

BST vs Array Binary Search

Aspect	Array Binary Search	BST Search
Search	O(log n) avg	O(log n) avg, O(n) worst
Insert	O(n) to keep sorted	O(log n) avg
Delete	O(n)	O(log n) avg
Data Order	Must maintain manually	Built-in structure
Use Case	Static data	Dynamic data

When to Use BSTs

BSTs are great for:

Dynamic searching: Data changes frequently
Ordered data: You need sorted output often
Auto-balancing variants: AVL and Red-Black trees for guaranteed O(log n)
Range queries: Finding all values in a range
Implementing maps/sets with ordered keys

Quiz Time

Validate what you’ve learned in this lesson by attempting these quiz questions: