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.