Binary Search Trees: Like a Phone Book

Welcome back! You learned about basic binary trees (like family trees). Now let’s learn about Binary Search Trees - special trees that keep data organized for super-fast searching!

What Makes a BST Special? (Phone Book Analogy)

The Phone Book Rule

Imagine a phone book where names are organized alphabetically:

A names come first
Z names come last
Everything is in perfect alphabetical order

A Binary Search Tree follows similar rules:

Left side: Smaller values (like A-M in phone book)
Right side: Larger values (like N-Z in phone book)
Perfect order: Everything stays organized automatically!

The Magic Rule

BST Rule: For any number in the tree:

Everything in its left subtree is smaller
Everything in its right subtree is larger

Building Your First BST

Let’s create a phone book tree:

// A contact in our phone book
type Contact struct {
    name  string
    phone string
    left  *Contact  // People with names before this one
    right *Contact  // People with names after this one
}

// Our phone book
type PhoneBook struct {
    root *Contact
}

Adding Contacts (Insert)

func (pb *PhoneBook) addContact(name, phone string) {
    pb.root = addContactHelper(pb.root, name, phone)
}

func addContactHelper(node *Contact, name, phone string) *Contact {
    // Empty spot? Add contact here!
    if node == nil {
        return &Contact{name: name, phone: phone}
    }
    
    // Compare names alphabetically
    if name < node.name {
        // Name comes before - go left
        node.left = addContactHelper(node.left, name, phone)
    } else if name > node.name {
        // Name comes after - go right
        node.right = addContactHelper(node.right, name, phone)
    }
    // Same name? Skip (no duplicates)
    
    return node
}

// Let's add some contacts
book := &PhoneBook{}
book.addContact("Alice", "555-0101")
book.addContact("Bob", "555-0102")
book.addContact("Charlie", "555-0103")
book.addContact("Zoe", "555-0199")

// The tree looks like:
//      Charlie
//     /       \
//  Bob       Zoe
//  /
// Alice

Finding a Contact (Search)

func (pb *PhoneBook) findContact(name string) string {
    return findContactHelper(pb.root, name)
}

func findContactHelper(node *Contact, name string) string {
    // Not found!
    if node == nil {
        return "Contact not found"
    }
    
    if name == node.name {
        // Found it!
        return node.phone
    } else if name < node.name {
        // Look left (earlier in alphabet)
        return findContactHelper(node.left, name)
    } else {
        // Look right (later in alphabet)
        return findContactHelper(node.right, name)
    }
}

// Search examples
phone := book.findContact("Bob")        // "555-0102"
phone := book.findContact("David")      // "Contact not found"

Real Life Example: Number Organizer

type NumberTree struct {
    root *NumberNode
}

type NumberNode struct {
    value int
    left  *NumberNode
    right *NumberNode
}

func (nt *NumberTree) insert(num int) {
    nt.root = insertHelper(nt.root, num)
}

func insertHelper(node *NumberNode, num int) *NumberNode {
    if node == nil {
        return &NumberNode{value: num}
    }
    
    if num < node.value {
        node.left = insertHelper(node.left, num)
    } else if num > node.value {
        node.right = insertHelper(node.right, num)
    }
    // Skip duplicates
    
    return node
}

func (nt *NumberTree) search(num int) bool {
    return searchHelper(nt.root, num)
}

func searchHelper(node *NumberNode, num int) bool {
    if node == nil {
        return false
    }
    
    if num == node.value {
        return true
    } else if num < node.value {
        return searchHelper(node.left, num)
    } else {
        return searchHelper(node.right, num)
    }
}

func main() {
    tree := &NumberTree{}
    
    // Add numbers
    numbers := []int{50, 30, 70, 20, 40, 60, 80}
    for _, num := range numbers {
        tree.insert(num)
    }
    
    // The tree:
    //      50
    //     /  \
    //   30    70
    //  / \   / \
    // 20 40 60 80
    
    // Search
    fmt.Println(tree.search(40))  // true
    fmt.Println(tree.search(25))  // false
}

Why BSTs Are Super Fast

Regular Search vs BST Search

Finding a number in a list:

List: [20, 30, 40, 50, 60, 70, 80]
Check each number one by one (slow!)

Finding a number in BST:

Start at 50
40 < 50? Go left to 30
40 > 30? Go right to 40
Found in 3 steps!

Speed comparison:

List: Check up to 7 numbers
BST: Check only 3 numbers (log₂7 ≈ 2.8)

Finding Extreme Values

Find Smallest Number (Leftmost)

func (nt *NumberTree) findSmallest() int {
    if nt.root == nil {
        return -1
    }
    
    // Keep going left until you can't go further
    current := nt.root
    for current.left != nil {
        current = current.left
    }
    
    return current.value
}

// In our tree: finds 20

Find Largest Number (Rightmost)

func (nt *NumberTree) findLargest() int {
    if nt.root == nil {
        return -1
    }
    
    // Keep going right until you can't go further
    current := nt.root
    for current.right != nil {
        current = current.right
    }
    
    return current.value
}

// In our tree: finds 80

The Special Power: In-Order Traversal

When you traverse a BST in-order (left, root, right), you get everything in sorted order!

func (nt *NumberTree) getSortedNumbers() []int {
    result := []int{}
    inOrderHelper(nt.root, &result)
    return result
}

func inOrderHelper(node *NumberNode, result *[]int) {
    if node == nil {
        return
    }
    
    // Left first
    inOrderHelper(node.left, result)
    
    // Then current
    *result = append(*result, node.value)
    
    // Then right
    inOrderHelper(node.right, result)
}

// Result: [20, 30, 40, 50, 60, 70, 80] - perfectly sorted!

Real Life Example: Dictionary Tree

type Dictionary struct {
    root *WordNode
}

type WordNode struct {
    word  string
    left  *WordNode
    right *WordNode
}

func (d *Dictionary) addWord(word string) {
    d.root = addWordHelper(d.root, word)
}

func addWordHelper(node *WordNode, word string) *WordNode {
    if node == nil {
        return &WordNode{word: word}
    }
    
    if word < node.word {
        node.left = addWordHelper(node.left, word)
    } else if word > node.word {
        node.right = addWordHelper(node.right, word)
    }
    
    return node
}

func (d *Dictionary) findWord(word string) bool {
    return findWordHelper(d.root, word)
}

func findWordHelper(node *WordNode, word string) bool {
    if node == nil {
        return false
    }
    
    if word == node.word {
        return true
    } else if word < node.word {
        return findWordHelper(node.left, word)
    } else {
        return findWordHelper(node.right, word)
    }
}

func (d *Dictionary) getAllWords() []string {
    result := []string{}
    collectWords(d.root, &result)
    return result
}

func collectWords(node *WordNode, result *[]string) {
    if node == nil {
        return
    }
    
    collectWords(node.left, result)
    *result = append(*result, node.word)
    collectWords(node.right, result)
}

func main() {
    dict := &Dictionary{}
    
    words := []string{"apple", "banana", "cherry", "date", "elderberry"}
    for _, word := range words {
        dict.addWord(word)
    }
    
    // All words in alphabetical order
    allWords := dict.getAllWords()
    fmt.Println(allWords)  // [apple, banana, cherry, date, elderberry]
    
    // Search
    fmt.Println(dict.findWord("cherry"))  // true
    fmt.Println(dict.findWord("grape"))   // false
}

BST Challenges

Challenge 1: Number Range Finder

Find all numbers between two values:

func (nt *NumberTree) findInRange(low, high int) []int {
    result := []int{}
    // Your code here
    // Hint: Use in-order traversal with range check
    return result
}

Challenge 2: Tree Height Calculator

Calculate how tall the tree is:

func (nt *NumberTree) getHeight() int {
    // Your code here
    // Hint: Max of left height + right height + 1
    return 0
}

Challenge 3: Closest Number Finder

Find the number in the tree closest to a target:

func (nt *NumberTree) findClosest(target int) int {
    // Your code here
    // Hint: Keep track of closest as you search
    return 0
}

Challenge 4: Tree Balancer

Check if the tree is balanced (similar heights on both sides):

func (nt *NumberTree) isBalanced() bool {
    // Your code here
    // Hint: Compare left and right subtree heights
    return false
}

Challenge 5: Duplicate Counter

Count how many times each number appears:

func (nt *NumberTree) countDuplicates() map[int]int {
    // Your code here
    // Hint: Use a map to count during traversal
    return nil
}

Real World Uses of BSTs

BSTs are used everywhere:

Phone Books: Names in alphabetical order
Dictionaries: Words in alphabetical order
File Systems: Files organized by name
Databases: Fast data lookup and sorting
Auto-complete: Quick word suggestions
Spell Check: Fast word validation

BST vs Regular Arrays

Operation	Array	BST (Balanced)
Search	O(n)	O(log n)
Insert	O(n)	O(log n)
Delete	O(n)	O(log n)
Sorted?	Maybe	Always!

Practice Time!

Exercise 1: Student Grade Organizer

Create a BST to store student grades:

Add students with their grades
Find a student’s grade quickly
List all students in grade order

Exercise 2: Library Book Catalog

Build a library system:

Books organized by title
Quick book lookup
Books in alphabetical order

Exercise 3: Price Comparison

Store product prices:

Find cheapest product
Find most expensive product
Find products in price range

Exercise 4: Calendar Events

Organize events by date:

Add events with dates
Find events on specific date
List events in chronological order

Exercise 5: Music Playlist

Create a music library:

Songs organized by title
Quick song search
Alphabetical song list

What’s Next?

Excellent! You now understand Binary Search Trees. Next, we’ll learn about Sorting Algorithms - different ways to arrange data in order!

Quick Quiz

What’s the main rule of a Binary Search Tree?
Why are BSTs faster than regular lists for searching?
What order do you get when traversing a BST in-order?
Where would you put a smaller number in a BST?
Name three real-life examples of BSTs.

Remember: BSTs are like phone books - everything stays perfectly organized for super-fast lookup!

Popular Topics

Categories