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.