Tree vs Array vs Linked List When Hierarchy Matters in DSA Go - Trade-offs & Analysis

Mental Model

A tree shows clear parent-child links for hierarchy, arrays list items flatly, and linked lists chain items linearly.

Analogy: Think of a family tree (tree) showing generations, a photo album (array) showing pictures side by side, and a treasure map trail (linked list) showing one step after another.

Tree:
    1
   / \
  2   3
 /   / \
4   5   6

Array:
[1][2][3][4][5][6]

Linked List:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

Dry Run Walkthrough

Input: Tree with nodes 1 as root, 2 and 3 as children, 4 child of 2, 5 and 6 children of 3; Array with elements [1,2,3,4,5,6]; Linked List with nodes 1->2->3->4->5->6

Goal: Show how hierarchy is represented differently in tree, array, and linked list

Step 1: Look at tree root node 1 with two children 2 and 3

Tree:
    1 ↑
   / \
  2   3
Array:
[1][2][3][4][5][6]
Linked List:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

Why: Tree shows parent-child links clearly, array and linked list do not

Step 2: Check children of node 2 and 3 in tree

Tree:
    1
   / \
  2 ↑  3
 /    / \
4    5   6
Array:
[1][2][3][4][5][6]
Linked List:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

Why: Tree shows hierarchy deeper, array and linked list remain flat or linear

Step 3: Observe array elements are stored sequentially without hierarchy

Tree:
    1
   / \
  2    3
 /    / \
4    5   6
Array:
[1][2][3][4][5][6] ↑
Linked List:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

Why: Array stores data contiguously but does not show parent-child relationships

Step 4: Observe linked list nodes connected one after another linearly

Tree:
    1
   / \
  2    3
 /    / \
4    5   6
Array:
[1][2][3][4][5][6]
Linked List:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null ↑

Why: Linked list shows order but no branching hierarchy

Result:

Tree:
    1
   / \
  2    3
 /    / \
4    5   6
Array:
[1][2][3][4][5][6]
Linked List:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

Annotated Code

DSA Go

package main

import "fmt"

// TreeNode represents a node in a tree
type TreeNode struct {
	Val      int
	Children []*TreeNode
}

// PrintTree prints tree nodes with indentation to show hierarchy
func PrintTree(node *TreeNode, level int) {
	if node == nil {
		return
	}
	for i := 0; i < level; i++ {
		fmt.Print("  ")
	}
	fmt.Println(node.Val)
	for _, child := range node.Children {
		PrintTree(child, level+1) // recurse to print children with indent
	}
}

// PrintArray prints array elements in one line
func PrintArray(arr []int) {
	fmt.Print("[")
	for i, v := range arr {
		fmt.Print(v)
		if i != len(arr)-1 {
			fmt.Print(", ")
		}
	}
	fmt.Println("]")
}

// ListNode represents a node in a linked list
type ListNode struct {
	Val  int
	Next *ListNode
}

// PrintLinkedList prints linked list nodes in order
func PrintLinkedList(head *ListNode) {
	curr := head
	for curr != nil {
		fmt.Printf("%d", curr.Val)
		if curr.Next != nil {
			fmt.Print(" -> ")
		}
		curr = curr.Next // advance to next node
	}
	fmt.Println(" -> null")
}

func main() {
	// Build tree
	root := &TreeNode{Val: 1}
	child2 := &TreeNode{Val: 2}
	child3 := &TreeNode{Val: 3}
	child4 := &TreeNode{Val: 4}
	child5 := &TreeNode{Val: 5}
	child6 := &TreeNode{Val: 6}
	child2.Children = []*TreeNode{child4}
	child3.Children = []*TreeNode{child5, child6}
	root.Children = []*TreeNode{child2, child3}

	// Array
	arr := []int{1, 2, 3, 4, 5, 6}

	// Linked List
	head := &ListNode{Val: 1}
	n2 := &ListNode{Val: 2}
	n3 := &ListNode{Val: 3}
	n4 := &ListNode{Val: 4}
	n5 := &ListNode{Val: 5}
	n6 := &ListNode{Val: 6}
	head.Next = n2
	n2.Next = n3
	n3.Next = n4
	n4.Next = n5
	n5.Next = n6

	fmt.Println("Tree structure:")
	PrintTree(root, 0)

	fmt.Println("Array elements:")
	PrintArray(arr)

	fmt.Println("Linked List nodes:")
	PrintLinkedList(head)
}

for _, child := range node.Children { PrintTree(child, level+1)

recurse to print each child with increased indentation to show hierarchy

curr = curr.Next // advance to next node

move forward in linked list to print nodes in order

Output

Tree structure:

1

  2

    4

  3

    5

    6

Array elements:

[1, 2, 3, 4, 5, 6]

Linked List nodes:

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

Complexity Analysis

Time: O(n) because each structure is printed by visiting each element once

Space: O(h) for tree due to recursion stack where h is tree height; O(1) for array and linked list printing

vs Alternative: Tree uses pointers to represent hierarchy explicitly, arrays store data contiguously but no hierarchy, linked lists store linear order with pointers but no branching

Edge Cases

Empty tree, array, or linked list

Print functions handle nil or empty inputs gracefully without errors

DSA Go

if node == nil { return } in PrintTree and curr != nil loop in PrintLinkedList

Single node/tree with one element

Prints single element correctly with no children or next nodes

DSA Go

for _, child := range node.Children loop handles zero children

When to Use This Pattern

When a problem involves parent-child relationships or hierarchy, think of trees; when order matters without hierarchy, arrays or linked lists fit better.

Common Mistakes

Mistake: Trying to represent hierarchy using arrays or linked lists directly without extra info
Fix: Use tree nodes with child pointers to capture hierarchy explicitly

Summary

Shows how trees represent hierarchy with parent-child links, arrays store flat sequences, and linked lists chain nodes linearly.

Use trees when you need to model branching relationships; arrays or linked lists when order matters without hierarchy.

The key insight is that trees explicitly show hierarchy via pointers to children, unlike arrays or linked lists.

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