Binary Trees: Like Family Trees

Welcome! You’ve learned about stacks and queues. Now let’s explore Trees - one of the most important data structures!

What is a Tree? (Real Life Analogy)

The Family Tree

Imagine your family tree:

Grandparents at the top
Parents in the middle
You and your siblings at the bottom
Each person connects to their children

That’s exactly how a tree works in programming!

Tree Rules:

Starts with one root (like grandparents)
Each item can have children (like parents having kids)
Items with no children are called leaves (like you, if you have no kids yet)
Information flows from top to bottom

Binary Trees: Each Parent Has At Most 2 Children

A Binary Tree is a special tree where each parent can have at most 2 children:

Left child (like your older sibling)
Right child (like your younger sibling)

Building Your First Tree

Let’s create a simple family tree:

// Each person in our family tree
type Person struct {
    name     string      // Person's name
    left     *Person     // Left child (older child)
    right    *Person     // Right child (younger child)
}

// Create family members
func main() {
    // Grandparents (root of our tree)
    grandpa := &Person{name: "Grandpa"}
    grandma := &Person{name: "Grandma"}
    
    // Parents
    dad := &Person{name: "Dad"}
    mom := &Person{name: "Mom"}
    
    // Children
    you := &Person{name: "You"}
    sibling := &Person{name: "Sibling"}
    
    // Build the family tree
    grandpa.left = dad      // Dad is grandpa's left child
    grandpa.right = mom     // Mom is grandpa's right child
    
    dad.left = you          // You are dad's left child
    dad.right = sibling     // Sibling is dad's right child
}

Tree Vocabulary (Like Learning a New Language)

The Family Members

type TreeNode struct {
    value       int         // The data (like age, name, etc.)
    leftChild   *TreeNode   // Left child
    rightChild  *TreeNode   // Right child
}

Tree Parts:

Root: The top person (grandpa) - no parent
Node: Any person in the tree
Parent: A person who has children
Child: A person who has a parent
Leaf: A person with no children (end of the line)
Branch: The connection between parent and child

Walking Through the Family Tree

Method 1: Visit Everyone (Traversal)

There are different ways to “visit” everyone in the family:

1. Preorder: Meet the Parent First, Then Children

Like introducing family: “This is grandpa, his son dad, dad’s son you…“

func visitFamilyPreorder(person *Person) {
    if person == nil {
        return
    }
    
    // 1. Meet the person first
    fmt.Printf("Meeting: %s\n", person.name)
    
    // 2. Then meet their left child
    visitFamilyPreorder(person.left)
    
    // 3. Then meet their right child
    visitFamilyPreorder(person.right)
}

// Output:
// Meeting: Grandpa
// Meeting: Dad
// Meeting: You
// Meeting: Sibling
// Meeting: Mom

2. Inorder: Meet Left Child, Parent, Right Child

Like reading left to right: “You, then Dad, then Sibling”

func visitFamilyInorder(person *Person) {
    if person == nil {
        return
    }
    
    // 1. Meet left child first
    visitFamilyInorder(person.left)
    
    // 2. Then meet the person
    fmt.Printf("Meeting: %s\n", person.name)
    
    // 3. Then meet right child
    visitFamilyInorder(person.right)
}

// Output:
// Meeting: You
// Meeting: Dad
// Meeting: Sibling
// Meeting: Grandpa
// Meeting: Mom

3. Postorder: Meet Children First, Then Parent

Like saying goodbye: “Goodbye kids, goodbye parents, goodbye grandparents”

func visitFamilyPostorder(person *Person) {
    if person == nil {
        return
    }
    
    // 1. Meet left child first
    visitFamilyPostorder(person.left)
    
    // 2. Meet right child
    visitFamilyPostorder(person.right)
    
    // 3. Meet the person last
    fmt.Printf("Goodbye: %s\n", person.name)
}

// Output:
// Goodbye: You
// Goodbye: Sibling
// Goodbye: Dad
// Goodbye: Mom
// Goodbye: Grandpa

4. Level Order: Meet Generation by Generation

Like meeting by age groups: “First grandparents, then parents, then children”

func visitFamilyByGeneration(root *Person) {
    if root == nil {
        return
    }
    
    // Use a queue to process generation by generation
    queue := []*Person{root}
    
    for len(queue) > 0 {
        // Get next person in line
        current := queue[0]
        queue = queue[1:]
        
        fmt.Printf("Generation member: %s\n", current.name)
        
        // Add their children to the queue
        if current.left != nil {
            queue = append(queue, current.left)
        }
        if current.right != nil {
            queue = append(queue, current.right)
        }
    }
}

// Output:
// Generation member: Grandpa
// Generation member: Dad
// Generation member: Mom
// Generation member: You
// Generation member: Sibling

Real Life Example: File Folder Structure

type FileNode struct {
    name     string
    isFile   bool
    left     *FileNode  // Could be a subfolder or file
    right    *FileNode  // Could be another subfolder or file
}

func createFileSystem() *FileNode {
    // Root folder
    root := &FileNode{name: "C:", isFile: false}
    
    // Program Files folder
    programFiles := &FileNode{name: "Program Files", isFile: false}
    
    // Windows folder
    windows := &FileNode{name: "Windows", isFile: false}
    
    // Some files
    notepad := &FileNode{name: "notepad.exe", isFile: true}
    calc := &FileNode{name: "calc.exe", isFile: true}
    
    // Build the structure
    root.left = programFiles
    root.right = windows
    
    programFiles.left = notepad
    windows.left = calc
    
    return root
}

func listAllFiles(folder *FileNode) {
    if folder == nil {
        return
    }
    
    if folder.isFile {
        fmt.Printf("File: %s\n", folder.name)
    } else {
        fmt.Printf("Folder: %s\n", folder.name)
    }
    
    listAllFiles(folder.left)
    listAllFiles(folder.right)
}

Real Life Example: Company Organization Chart

type Employee struct {
    name        string
    position    string
    left        *Employee  // Left subordinate
    right       *Employee  // Right subordinate
}

func createOrgChart() *Employee {
    // CEO at the top
    ceo := &Employee{name: "Alice", position: "CEO"}
    
    // Department heads
    cto := &Employee{name: "Bob", position: "CTO"}
    cfo := &Employee{name: "Carol", position: "CFO"}
    
    // Engineers
    engineer1 := &Employee{name: "David", position: "Senior Engineer"}
    engineer2 := &Employee{name: "Eve", position: "Engineer"}
    
    // Accountants
    accountant1 := &Employee{name: "Frank", position: "Senior Accountant"}
    
    // Build organization
    ceo.left = cto
    ceo.right = cfo
    
    cto.left = engineer1
    cto.right = engineer2
    
    cfo.left = accountant1
    
    return ceo
}

func printOrgChart(employee *Employee, level int) {
    if employee == nil {
        return
    }
    
    // Print with indentation
    indent := ""
    for i := 0; i < level; i++ {
        indent += "  "
    }
    
    fmt.Printf("%s%s (%s)\n", indent, employee.name, employee.position)
    
    printOrgChart(employee.left, level+1)
    printOrgChart(employee.right, level+1)
}

Tree Measurements

How Tall is the Tree? (Height)

func getTreeHeight(root *TreeNode) int {
    if root == nil {
        return 0  // Empty tree has height 0
    }
    
    // Get height of left and right subtrees
    leftHeight := getTreeHeight(root.leftChild)
    rightHeight := getTreeHeight(root.rightChild)
    
    // Height is 1 + the taller subtree
    if leftHeight > rightHeight {
        return leftHeight + 1
    }
    return rightHeight + 1
}

// Example tree:
//     1
//    / \
//   2   3
//  /
// 4
//
// Height = 3 (levels: 1-2-3)

How Many People in the Family? (Count Nodes)

func countFamilyMembers(root *Person) int {
    if root == nil {
        return 0  // No family members
    }
    
    // Count: this person + left family + right family
    return 1 + countFamilyMembers(root.left) + countFamilyMembers(root.right)
}

Find the Oldest Person (Maximum Value)

func findOldest(root *TreeNode) int {
    if root == nil {
        return -1  // No one in family
    }
    
    // Check this person's age
    oldest := root.value
    
    // Check left family
    leftOldest := findOldest(root.leftChild)
    if leftOldest > oldest {
        oldest = leftOldest
    }
    
    // Check right family
    rightOldest := findOldest(root.rightChild)
    if rightOldest > oldest {
        oldest = rightOldest
    }
    
    return oldest
}

Special Types of Binary Trees

1. Full Binary Tree

Every person has either 0 children or 2 children (no single parents!)

2. Complete Binary Tree

All generations are full except the youngest, and they’re filled from left to right

3. Perfect Binary Tree

Every level is completely full (like a balanced family tree)

4. Balanced Binary Tree

Left and right sides are roughly equal height (fair family!)

Fun Tree Challenges

Challenge 1: Family Reunion Counter

Count how many people will attend the family reunion:

func countAttendees(root *Person) int {
    // Your code here
    // Hint: Count everyone in the tree
}

Challenge 2: Find Cousins

Find all people at the same level (generation) as a given person:

func findCousins(root *Person, targetName string) []string {
    // Your code here
    // Hint: Use level order traversal
}

Challenge 3: Family Tree Printer

Print the family tree with nice formatting:

func printFamilyTree(root *Person) {
    // Your code here
    // Hint: Use recursion with indentation
}

Challenge 4: Is the Tree Balanced?

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

func isFamilyBalanced(root *Person) bool {
    // Your code here
    // Hint: Compare left and right subtree heights
}

Challenge 5: Mirror Family Tree

Create a mirror image of the family tree (swap left and right):

func mirrorFamilyTree(root *Person) *Person {
    // Your code here
    // Hint: Swap left and right children recursively
}

Real World Uses of Trees

Trees are everywhere in programming:

File Systems: Folders inside folders
Organization Charts: Bosses and employees
HTML Documents: Nested tags
Game AI: Decision trees
Databases: Index structures
Computer Networks: Routing tables

Practice Time!

Exercise 1: Animal Kingdom Tree

Create a tree showing animal classifications:

Animals
- Mammals (Dogs, Cats)
- Birds (Eagles, Sparrows)
- Fish (Sharks, Goldfish)

Exercise 2: Recipe Book

Organize recipes in a tree:

Cooking
- Breakfast (Pancakes, Eggs)
- Lunch (Sandwiches, Salads)
- Dinner (Pasta, Steak)

Exercise 3: Shopping Categories

Create a shopping tree:

Store
- Electronics (Phones, Laptops)
- Clothing (Shirts, Pants)
- Food (Fruits, Vegetables)

Exercise 4: Sports Tournament

Build a tournament bracket tree:

Final
- Semi 1 (Team A vs Team B)
- Semi 2 (Team C vs Team D)

Exercise 5: Course Curriculum

Organize course topics:

Programming
- Basics (Variables, Loops)
- Advanced (Functions, Classes)
- Projects (Games, Apps)

What’s Next?

Great! You now understand binary trees. Next, we’ll learn about Binary Search Trees - special trees that keep data organized for super-fast searching!

Quick Quiz

What’s the difference between a tree and a binary tree?
What are the three main ways to traverse a tree?
What’s a leaf node?
How do you calculate the height of a tree?
Name three real-life examples of trees.

Remember: Trees are like family trees - they start with one root and branch out to many leaves!

Popular Topics

Categories