0
0
DSA Goprogramming~10 mins

Prefix Search Using Trie in DSA Go - Interactive Practice

Choose your learning style9 modes available
LearnWhyDeepVisualTryChallengeProjectRecallTime
Practice - 5 Tasks
Answer the questions below
1fill in blank
easy

Complete the code to insert a word into the trie.

DSA Go
func (t *Trie) Insert(word string) {
    node := t.root
    for _, ch := range word {
        if node.children[ch] == nil {
            node.children[ch] = &TrieNode{children: make(map[rune]*TrieNode)}
        }
        node = node.children[[1]]
    }
    node.isEnd = true
}
Drag options to blanks, or click blank then click option'
Ach
Bword
Cnode
Dt
Attempts:
3 left
💡 Hint
Common Mistakes
Using the whole word instead of the current character.
Using the node variable incorrectly.
2fill in blank
medium

Complete the code to check if a prefix exists in the trie.

DSA Go
func (t *Trie) StartsWith(prefix string) bool {
    node := t.root
    for _, ch := range prefix {
        if node.children[[1]] == nil {
            return false
        }
        node = node.children[ch]
    }
    return true
}
Drag options to blanks, or click blank then click option'
Aprefix
Bch
Cnode
Dt
Attempts:
3 left
💡 Hint
Common Mistakes
Using the whole prefix string instead of the current character.
Checking the wrong variable for children.
3fill in blank
hard

Fix the error in the search function to correctly find a word in the trie.

DSA Go
func (t *Trie) Search(word string) bool {
    node := t.root
    for _, ch := range word {
        if node.children[ch] == nil {
            return false
        }
        node = node.children[ch]
    }
    return node.[1]
}
Drag options to blanks, or click blank then click option'
Aword
Bchildren
Croot
DisEnd
Attempts:
3 left
💡 Hint
Common Mistakes
Returning the children map instead of the end flag.
Returning the root or word variable incorrectly.
4fill in blank
hard

Fill both blanks to implement a function that returns all words with a given prefix.

DSA Go
func (t *Trie) WordsWithPrefix(prefix string) []string {
    node := t.root
    for _, ch := range prefix {
        if node.children[ch] == nil {
            return nil
        }
        node = node.children[ch]
    }
    var results []string
    var dfs func(n *TrieNode, path string)
    dfs = func(n *TrieNode, path string) {
        if n.[1] {
            results = append(results, path)
        }
        for c, child := range n.[2] {
            dfs(child, path+string(c))
        }
    }
    dfs(node, prefix)
    return results
}
Drag options to blanks, or click blank then click option'
AisEnd
Bchildren
Croot
Dword
Attempts:
3 left
💡 Hint
Common Mistakes
Using wrong field names like 'root' or 'word' instead of 'children' or 'isEnd'.
Not appending words when 'isEnd' is true.
5fill in blank
hard

Fill all three blanks to implement a function that deletes a word from the trie.

DSA Go
func (t *Trie) Delete(word string) bool {
    var deleteHelper func(node *TrieNode, word string, depth int) bool
    deleteHelper = func(node *TrieNode, word string, depth int) bool {
        if node == nil {
            return false
        }
        if depth == len(word) {
            if !node.[1] {
                return false
            }
            node.[2] = false
            return len(node.[3]) == 0
        }
        ch := rune(word[depth])
        if deleteHelper(node.children[ch], word, depth+1) {
            delete(node.children, ch)
            return !node.[1] && len(node.children) == 0
        }
        return false
    }
    return deleteHelper(t.root, word, 0)
}
Drag options to blanks, or click blank then click option'
AisEnd
Cchildren
Droot
Attempts:
3 left
💡 Hint
Common Mistakes
Confusing 'root' with 'children' or 'isEnd'.
Not unsetting the 'isEnd' flag when deleting.