Tree vs Array vs Linked List When Hierarchy Matters in DSA Go - Build Both Approaches

Tree vs Array vs Linked List When Hierarchy Matters

📖 Scenario: Imagine you are organizing a company's employee structure. Each employee has a name and may have subordinates reporting to them. You want to represent this hierarchy in different ways to understand how data structures like arrays, linked lists, and trees can store hierarchical data.

🎯 Goal: You will create three different data structures in Go to represent the same employee hierarchy: an array, a linked list, and a tree. You will then print the structure to see how hierarchy is maintained or lost in each case.

📋 What You'll Learn

Create an array of employee names representing a flat list of employees.

Create a singly linked list of employee names representing a chain of command.

Create a tree structure where each employee node can have multiple subordinates.

Print each data structure to show how hierarchy is represented.

💡 Why This Matters

🌍 Real World

Hierarchical data structures like trees are used in organizations, file systems, and menus where relationships matter.

💼 Career

Understanding how to represent and traverse hierarchical data is essential for software developers working with complex data models.

1

Create an array of employee names

Create a variable called employeesArray which is a slice of strings containing these exact employee names in order: "CEO", "Manager", "Lead", "Developer".

DSA Go

# Create a slice of strings called employeesArray with the names "CEO", "Manager", "Lead", "Developer"
// Your code here

Hint

Use a slice literal with the exact employee names in order.

2

Create a singly linked list of employees

Add a struct type called EmployeeNode with fields name string and next *EmployeeNode. Then create variables head, node2, node3, and node4 of type *EmployeeNode representing employees "CEO", "Manager", "Lead", and "Developer" respectively. Link them in order so that head points to "CEO" and each node's next points to the next employee.

DSA Go

package main

import "fmt"

type EmployeeNode struct {
    name string
    next *EmployeeNode
}

func main() {
    employeesArray := []string{"CEO", "Manager", "Lead", "Developer"}

    // Create linked list nodes and link them
    // Your code here
}

Hint

Define the struct first, then create nodes with &EmployeeNode{...} and link them using the next field.

3

Create a tree structure for employee hierarchy

Add a struct type called EmployeeTreeNode with fields name string and subordinates []*EmployeeTreeNode. Create nodes for "CEO", "Manager", "Lead", and "Developer". Set up the hierarchy so that "CEO" has "Manager" as subordinate, "Manager" has "Lead" as subordinate, and "Lead" has "Developer" as subordinate.

DSA Go

package main

import "fmt"

type EmployeeNode struct {
    name string
    next *EmployeeNode
}

type EmployeeTreeNode struct {
    name string
    subordinates []*EmployeeTreeNode
}

func main() {
    employeesArray := []string{"CEO", "Manager", "Lead", "Developer"}

    head := &EmployeeNode{name: "CEO"}
    node2 := &EmployeeNode{name: "Manager"}
    node3 := &EmployeeNode{name: "Lead"}
    node4 := &EmployeeNode{name: "Developer"}

    head.next = node2
    node2.next = node3
    node3.next = node4

    // Create tree nodes and set hierarchy
    // Your code here
}

Hint

Define the tree node struct with a slice of pointers for subordinates. Create nodes and assign subordinates slices accordingly.

4

Print all three data structures to show hierarchy

Print the employeesArray slice on one line. Then print the linked list starting from head by traversing next pointers, printing each employee name separated by " -> ". Finally, write a recursive function printTree that takes an *EmployeeTreeNode and an indent string, prints the node's name prefixed by indent, and recursively prints subordinates with increased indentation. Call printTree(ceo, "") to print the tree hierarchy.

DSA Go

package main

import "fmt"

type EmployeeNode struct {
    name string
    next *EmployeeNode
}

type EmployeeTreeNode struct {
    name string
    subordinates []*EmployeeTreeNode
}

func main() {
    employeesArray := []string{"CEO", "Manager", "Lead", "Developer"}

    head := &EmployeeNode{name: "CEO"}
    node2 := &EmployeeNode{name: "Manager"}
    node3 := &EmployeeNode{name: "Lead"}
    node4 := &EmployeeNode{name: "Developer"}

    head.next = node2
    node2.next = node3
    node3.next = node4

    ceo := &EmployeeTreeNode{name: "CEO"}
    manager := &EmployeeTreeNode{name: "Manager"}
    lead := &EmployeeTreeNode{name: "Lead"}
    developer := &EmployeeTreeNode{name: "Developer"}

    ceo.subordinates = []*EmployeeTreeNode{manager}
    manager.subordinates = []*EmployeeTreeNode{lead}
    lead.subordinates = []*EmployeeTreeNode{developer}

    // Print all data structures
    // Your code here
}

// Add printTree function below
// Your code here

Hint

Use a loop to print the linked list with arrows. Use recursion to print the tree with indentation.

Practice

1. Which data structure is best suited to represent hierarchical relationships like a family tree?

easy

A. Tree

B. Array

C. Linked List

D. Hash Map

Solution

1. Step 1: Understand hierarchy representation

   Hierarchies require parent-child relationships, which trees naturally represent.

2. Step 2: Compare data structures

   Arrays and linked lists are linear and do not represent branching well; trees do.

3. Final Answer:

   Tree -> Option A

4. Quick Check:

   Hierarchy needs branching = Tree [OK]

Hint: Hierarchy means branching; trees model branching best [OK]

Common Mistakes:

• Choosing array for hierarchy
• Confusing linked list with tree
• Ignoring parent-child links

2. Which of the following is the correct way to declare a slice of integers in Go?

easy

A. var nums [5]int

B. var nums (int)

C. var nums int[]

D. var nums []int

Solution

1. Step 1: Recall Go slice syntax

   Slices are declared with [] before the type, like []int.

2. Step 2: Check options

   var nums []int uses var nums []int which is correct slice declaration.

3. Final Answer:

   var nums []int -> Option D

4. Quick Check:

   Slice syntax = []type [OK]

Hint: Slices use []type syntax, arrays use [size]type [OK]

Common Mistakes:

• Using array syntax for slices
• Placing brackets after type
• Using parentheses instead of brackets

3. Consider the following Go code that builds a simple tree node struct and links children:

package main
import "fmt"

type Node struct {
    value int
    children []*Node
}

func main() {
    root := &Node{value: 1}
    child1 := &Node{value: 2}
    child2 := &Node{value: 3}
    root.children = append(root.children, child1, child2)
    fmt.Println(root.children[1].value)
}

What is the output of this program?

medium

A. 3

B. 2

C. 1

D. Compilation error

Solution

1. Step 1: Understand tree node structure

   Root node has value 1 and two children with values 2 and 3.

2. Step 2: Trace the print statement

   root.children[1] accesses second child, which has value 3, so prints 3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Second child value = 3 [OK]

Hint: Index 1 in children slice is second child [OK]

Common Mistakes:

• Confusing index 0 and 1
• Assuming root value prints
• Thinking children is a single node

4. The following Go code attempts to create a linked list node and print its value:

package main
import "fmt"

type Node struct {
    value int
    next *Node
}

func main() {
    node := Node{value: 10}
    fmt.Println(node.next.value)
}

What is the issue with this code?

medium

A. Missing import for fmt package

B. Syntax error in struct declaration

C. node.next is nil, accessing value causes runtime panic

D. node.value is uninitialized

Solution

1. Step 1: Analyze node initialization

   node.next is not set, so it is nil by default.

2. Step 2: Accessing node.next.value

   Accessing value on nil pointer causes runtime panic (nil dereference).

3. Final Answer:

   node.next is nil, accessing value causes runtime panic -> Option C

4. Quick Check:

   Nil pointer access causes panic [OK]

Hint: Check for nil before accessing pointer fields [OK]

Common Mistakes:

• Ignoring nil pointer dereference
• Assuming default values for pointers
• Missing import is not the main issue

5. You need to store a company's organizational chart where each employee can have multiple direct reports. Which data structure is best and why? Options: A) Use an array because it stores elements contiguously. B) Use a tree because it naturally models hierarchical relationships. C) Use a linked list because it allows easy insertion. D) Use a hash map because it provides fast lookups.

medium

A. Use an array because it stores elements contiguously.

B. Use a tree because it naturally models hierarchical relationships.

C. Use a linked list because it allows easy insertion.

D. Use a hash map because it provides fast lookups.

Solution

1. Step 1: Understand organizational chart structure

   It is hierarchical with multiple direct reports per employee.

2. Step 2: Evaluate data structure suitability

   Arrays and linked lists are linear, not hierarchical. Hash maps are for key-value pairs, not hierarchy.

3. Step 3: Choose tree for hierarchy

   Trees model parent-child relationships naturally, perfect for org charts.

4. Final Answer:

   Use a tree because it naturally models hierarchical relationships. -> Option B

5. Quick Check:

   Hierarchy needs tree structure [OK]

Hint: Hierarchy means tree; arrays and lists are linear [OK]

Common Mistakes:

• Choosing array or list for hierarchy
• Confusing fast lookup with hierarchy modeling
• Ignoring multiple children per node