Why Trees Exist and What Linked Lists and Arrays Cannot Do in DSA Go - Test Your Knowledge

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create a root node for a tree in Go.

DSA Go

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

root := &Node{value: [1], children: nil}

Drag options to blanks, or click blank then click option'

A"root"

Bnil

C0

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Using nil for the value field instead of an integer.

Using a string instead of an integer for the value.

The root node's value should be an integer, so 0 is a valid choice. nil is for pointers, and "root" is a string, which is incorrect here.

2fill in blank

medium

Complete the code to add a child node to the root node's children slice.

DSA Go

child := &Node{value: 1, children: nil}
root.children = append(root.children, [1])

Drag options to blanks, or click blank then click option'

Aroot

Bnil

C&child

Dchild

Attempts:

3 left

💡 Hint

Common Mistakes

Appending root instead of child.

Appending &child which is a pointer to a pointer.

We append the pointer to the child node, which is stored in variable 'child'.

3fill in blank

hard

Fix the error in the function that counts total nodes in a tree.

DSA Go

func countNodes(node *Node) int {
    if node == nil {
        return 0
    }
    count := 1
    for _, child := range node.children {
        count += [1](child)
    }
    return count
}

Drag options to blanks, or click blank then click option'

AcountNodes

Bcountnode

Ccountnodes

Dcount_Node

Attempts:

3 left

💡 Hint

Common Mistakes

Using incorrect capitalization in recursive call.

Using a different function name by mistake.

The function name is countNodes, so recursive calls must use the exact same name.

4fill in blank

hard

Fill both blanks to create a map of node values to their number of children.

DSA Go

func childrenCountMap(root *Node) map[int]int {
    result := make(map[int]int)
    var traverse func(node *Node)
    traverse = func(node *Node) {
        if node == nil {
            return
        }
        result[node.[1]] = len(node.[2])
        for _, child := range node.children {
            traverse(child)
        }
    }
    traverse(root)
    return result
}

Drag options to blanks, or click blank then click option'

Avalue

Bchildren

Cval

Dchild

Attempts:

3 left

💡 Hint

Common Mistakes

Using incorrect field names like val or child.

Using the wrong field for length calculation.

We use node.value as the key and len(node.children) as the value in the map.

5fill in blank

hard

Fill all three blanks to create a function that finds if a value exists in the tree.

DSA Go

func exists(node *Node, target int) bool {
    if node == nil {
        return false
    }
    if node.[1] == [2] {
        return true
    }
    for _, child := range node.[3] {
        if exists(child, target) {
            return true
        }
    }
    return false
}

Drag options to blanks, or click blank then click option'

Avalue

Btarget

Cchildren

Dval

Attempts:

3 left

💡 Hint

Common Mistakes

Using incorrect field names like val instead of value.

Comparing to the wrong variable.

Iterating over a wrong field.

We compare node.value to target and iterate over node.children to search recursively.

Practice

1. Why do trees exist as a data structure when we already have linked lists and arrays?

easy

A. Because trees allow hierarchical data representation which arrays and linked lists cannot efficiently provide

B. Because trees use less memory than arrays and linked lists

C. Because trees are easier to implement than arrays and linked lists

D. Because trees always provide faster access than arrays and linked lists

Solution

1. Step 1: Understand the limitation of arrays and linked lists

   Arrays and linked lists store data in a linear sequence, which makes representing hierarchical relationships difficult.

2. Step 2: Identify the advantage of trees

   Trees allow data to be stored in a hierarchy, like a family tree or file system, which arrays and linked lists cannot efficiently represent.

3. Final Answer:

   Trees allow hierarchical data representation which arrays and linked lists cannot efficiently provide -> Option A

4. Quick Check:

   Hierarchical data needs trees = B [OK]

Hint: Trees represent hierarchy; arrays and lists are linear [OK]

Common Mistakes:

• Thinking trees always use less memory
• Assuming trees are easier to implement
• Believing trees always have faster access

2. Which of the following is the correct way to declare a simple binary tree node struct in Go?

easy

A. type Node struct { value int; left *Node; right *Node }

B. type Node struct { value int; left Node; right Node }

C. type Node struct { value int; left *int; right *int }

D. type Node struct { value int; left int; right int }

Solution

1. Step 1: Understand pointer usage in tree nodes

   Each node's left and right children must be pointers to other nodes to allow recursive structure.

2. Step 2: Check each option's correctness

   type Node struct { value int; left *Node; right *Node } uses pointers to Node for left and right, which is correct. type Node struct { value int; left Node; right Node } uses Node directly, causing infinite size. Options C and D use incorrect types for children.

3. Final Answer:

   type Node struct { value int; left *Node; right *Node } -> Option A

4. Quick Check:

   Tree nodes use pointers to child nodes = A [OK]

Hint: Tree children must be pointers to nodes in Go [OK]

Common Mistakes:

• Using non-pointer types for child nodes
• Using primitive types instead of node pointers
• Forgetting semicolons or commas in struct

3. You want to represent a company's organizational chart where each manager can have multiple direct reports. Why is a tree a better choice than arrays or linked lists for this structure?

easy

A. Because trees use less memory than arrays and linked lists

B. Because arrays can only store numbers, not objects

C. Because linked lists cannot store more than two elements

D. Because trees can represent multiple levels of hierarchy and branching relationships naturally

Solution

1. Step 1: Understand the organizational chart structure

   It has multiple levels and each manager can have many direct reports, forming a branching hierarchy.

2. Step 2: Compare data structures for hierarchy representation

   Arrays and linked lists are linear and cannot naturally represent multiple branches and levels. Trees model this branching well.

3. Step 3: Confirm why other options are incorrect

   Arrays can store objects, linked lists can store many elements, and trees do not necessarily use less memory.

4. Final Answer:

   Because trees can represent multiple levels of hierarchy and branching relationships naturally -> Option D

5. Quick Check:

   Hierarchical branching needs trees = A [OK]

Hint: Use trees for multi-level branching hierarchy [OK]

Common Mistakes:

• Thinking arrays cannot store objects
• Believing linked lists have size limits
• Assuming trees always use less memory

4. What will be the output of the following Go code that builds a simple binary tree and prints the root's left child's value?

package main
import "fmt"

type Node struct {
  value int
  left  *Node
  right *Node
}

func main() {
  root := &Node{value: 10}
  root.left = &Node{value: 5}
  root.right = &Node{value: 15}
  fmt.Println(root.left.value)
}

medium

A. 10

B. 15

C. 5

D. Compilation error

Solution

1. Step 1: Analyze tree construction

   Root node has value 10, left child value 5, right child value 15.

2. Step 2: Identify printed value

   Code prints root.left.value, which is 5.

3. Final Answer:

   5 -> Option C

4. Quick Check:

   root.left.value = 5 [OK]

Hint: Print root.left.value to get left child's value [OK]

Common Mistakes:

• Printing root.value instead of root.left.value
• Confusing left and right child values
• Assuming compilation error due to pointers

5. The following Go code attempts to create a binary tree node but has an error. What is the error?

type Node struct {
  value int
  left  *Node
  right *Node
}

func main() {
  root := Node{value: 10}
  root.left = Node{value: 5}
  root.right = &Node{value: 15}
}

medium

A. No error, code compiles and runs fine

B. Cannot assign Node value to a pointer field without using &

C. Cannot declare root as value type, must be pointer

D. Missing semicolon after struct definition

Solution

1. Step 1: Check field types and assignments

   left and right fields are pointers to Node (*Node).

2. Step 2: Identify incorrect assignment

   root.left = Node{value: 5} assigns a value type to a pointer field without using & to get address.

3. Final Answer:

   Cannot assign Node value to a pointer field without using & -> Option B

4. Quick Check:

   Pointer fields need address (&) for assignment = D [OK]

Hint: Pointer fields require & when assigning values [OK]

Common Mistakes:

• Ignoring pointer vs value type mismatch
• Thinking root must be a pointer
• Assuming missing semicolon causes error