Tree vs Array vs Linked List When Hierarchy Matters in DSA Go - Compare & Choose

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of traversing a simple tree structure

Given the following tree structure in Go, what is the output of the preorder traversal?

DSA Go

package main
import "fmt"
type Node struct {
    value int
    children []*Node
}

func preorder(n *Node) {
    if n == nil {
        return
    }
    fmt.Print(n.value, " -> ")
    for _, c := range n.children {
        preorder(c)
    }
}

func main() {
    root := &Node{value: 1}
    child1 := &Node{value: 2}
    child2 := &Node{value: 3}
    child3 := &Node{value: 4}
    root.children = []*Node{child1, child2}
    child1.children = []*Node{child3}
    preorder(root)
    fmt.Print("null")
}

A 1 -> 2 -> 3 -> 4 -> null

B 1 -> 3 -> 2 -> 4 -> null

C 2 -> 4 -> 1 -> 3 -> null

D 1 -> 2 -> 4 -> 3 -> null

💡 Hint

Preorder traversal visits the root first, then children from left to right.

Preorder traversal prints the current node value, then recursively visits each child in order. Here, root is 1, children are 2 and 3, and 2 has child 4. So output is 1 -> 2 -> 4 -> 3 -> null.

🧠 Conceptual

intermediate

Choosing data structure for hierarchical data with frequent insertions

Which data structure is best suited to represent a hierarchy where nodes are frequently inserted or removed at various levels?

A Linked List, because it allows efficient insertions and deletions at any position

B Tree, because it naturally represents hierarchical relationships and supports dynamic changes

C Array, because it allows fast random access to elements

D Stack, because it manages elements in a last-in-first-out order

💡 Hint

Think about which structure models hierarchy and supports dynamic changes well.

Trees represent hierarchy naturally and allow efficient insertions and deletions at any node. Arrays have fixed size and costly insertions/removals. Linked lists are linear and don't represent hierarchy well. Stacks are linear and follow LIFO order, not suitable for hierarchy.

🔧 Debug

advanced

Identify the bug in linked list hierarchy representation

Consider this Go code snippet representing a linked list node with a parent pointer to represent hierarchy. What is the bug that causes incorrect parent linkage?

DSA Go

type Node struct {
    value int
    next *Node
    parent *Node
}

func main() {
    root := &Node{value: 1}
    child := &Node{value: 2, parent: root}
    root.next = child
    child.parent = child
}

A The line 'child.parent = child' incorrectly sets the parent to itself instead of root

B The 'next' pointer should be nil for root node

C The 'parent' field should be of type int, not *Node

D The 'value' field is not initialized for child node

💡 Hint

Check the assignment of the parent pointer for the child node.

The line 'child.parent = child' mistakenly assigns the child's parent pointer to itself, breaking the hierarchy. It should remain 'child.parent = root' to correctly link the child to its parent.

❓ Predict Output

advanced

Output of converting tree to array with level order traversal

What is the output of the following Go code that performs a level order traversal (breadth-first) of a tree and stores values in an array?

DSA Go

package main
import "fmt"

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

func levelOrder(root *Node) []int {
    if root == nil {
        return []int{}
    }
    var result []int
    queue := []*Node{root}
    for len(queue) > 0 {
        current := queue[0]
        queue = queue[1:]
        result = append(result, current.value)
        for _, c := range current.children {
            queue = append(queue, c)
        }
    }
    return result
}

func main() {
    root := &Node{value: 10}
    c1 := &Node{value: 20}
    c2 := &Node{value: 30}
    c3 := &Node{value: 40}
    root.children = []*Node{c1, c2}
    c1.children = []*Node{c3}
    arr := levelOrder(root)
    fmt.Println(arr)
}

A [10 20 40 30]

B [10 30 20 40]

C [10 20 30 40]

D [20 30 40 10]

💡 Hint

Level order visits nodes level by level from left to right.

Level order traversal visits root first (10), then its children (20, 30), then the child of 20 which is 40. So the array is [10 20 30 40].

🧠 Conceptual

expert

Why linked list is not ideal for representing hierarchical data

Which of the following is the main reason linked lists are not ideal for representing hierarchical data structures?

A Linked lists do not support random access, making it hard to navigate hierarchy levels efficiently

B Linked lists use too much memory compared to arrays

C Linked lists cannot store data of different types

D Linked lists are immutable and cannot be changed after creation

💡 Hint

Think about how hierarchy navigation requires moving up and down levels quickly.

Hierarchical data requires moving between parent and child nodes efficiently. Linked lists are linear and do not support random access, making it inefficient to navigate hierarchy levels. Trees are better suited for this.

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