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.