Why Trees Exist and What Linked Lists and Arrays Cannot Do in DSA Go - See It Work

Why Trees Exist and What Linked Lists and Arrays Cannot Do

📖 Scenario: Imagine you are organizing a company's employee directory. You want to store employees so you can quickly find who reports to whom, and also find employees by their ID efficiently. You first tried using a list and then an array, but both had problems when the company grew.

🎯 Goal: You will create a simple tree structure in Go to represent employees and their direct reports. This will show why trees are useful and what linked lists and arrays cannot do well.

📋 What You'll Learn

Create a struct called Employee with fields id int and reports []*Employee

Create a root employee with id 1

Add two direct reports with ids 2 and 3 to the root employee

Add one direct report with id 4 to the employee with id 2

Print the tree structure showing each employee and their direct reports

💡 Why This Matters

🌍 Real World

Trees are used in many real-world applications like file systems, organizational charts, and website menus where data is hierarchical.

💼 Career

Understanding trees helps in software engineering roles that deal with complex data structures, databases, and efficient data retrieval.

1

Create the Employee struct and root employee

Create a struct called Employee with fields id int and reports []*Employee. Then create a variable called root of type *Employee with id 1 and an empty reports slice.

DSA Go

type Employee struct {
    id int
    reports []*Employee
}

// Create root employee with id 1
// Your code here

Hint

Define the struct with the fields exactly as stated. Then create root as a pointer to Employee with id: 1 and an empty slice for reports.

2

Add direct reports to the root employee

Create two new Employee pointers with id 2 and 3 and empty reports slices. Add them to the reports slice of the root employee.

DSA Go

package main

import "fmt"

type Employee struct {
    id int
    reports []*Employee
}

func main() {
    root := &Employee{id: 1, reports: []*Employee{}}
    // Add employees with id 2 and 3 as reports to root
    // Your code here
}

Hint

Create two new employees with ids 2 and 3 and add them to root.reports using append.

3

Add a direct report to employee with id 2

Create a new Employee pointer with id 4 and empty reports slice. Add it to the reports slice of the employee with id 2 (which is emp2).

DSA Go

package main

import "fmt"

type Employee struct {
    id int
    reports []*Employee
}

func main() {
    root := &Employee{id: 1, reports: []*Employee{}}
    emp2 := &Employee{id: 2, reports: []*Employee{}}
    emp3 := &Employee{id: 3, reports: []*Employee{}}
    root.reports = append(root.reports, emp2, emp3)
    // Add employee with id 4 as report to emp2
    // Your code here
}

Hint

Create employee 4 and append it to emp2.reports.

4

Print the tree structure showing employees and their reports

Write a function called printEmployee that takes an *Employee and an int level for indentation. It prints the employee's id with indentation, then recursively prints all direct reports with increased indentation. Call printEmployee(root, 0) in main to display the tree.

DSA Go

Hint

Use recursion to print each employee with indentation showing the tree structure. Call printEmployee(root, 0) in main.