🎙 Free live masterclass · Sun, 29 Nov, 7:00 pm IST · Java Full Stack roadmap Register free →
Skills101
← Quiz: Tries (Prefix Trees): all 15 questions

Quiz: Tries (Prefix Trees) · Question 6 of 15

What does this print? (code)

What does this print?

class N:
    def __init__(self):
        self.k, self.end = {}, False

root = N()
for w in ["bat", "ball", "bad", "cat"]:
    n = root
    for ch in w:
        n = n.k.setdefault(ch, N())
    n.end = True

def words(n, pre, out):
    if n.end:
        out.append(pre)
    for ch in sorted(n.k):
        words(n.k[ch], pre + ch, out)
    return out

n = root
for ch in "ba":
    n = n.k[ch]
print(words(n, "ba", []))
  1. A.['bat', 'ball', 'bad']
  2. B.['bad', 'ball', 'bat']
  3. C.['bad', 'ball', 'bat', 'cat']
  4. D.['ba']
Answer & explanation

Correct answer: ['bad', 'ball', 'bat']

After walking to "ba", the DFS visits children in sorted order: d, l, t.

Can you get the rest right without peeking?

Take the timed Quiz: Tries (Prefix Trees) quiz free. Pass it to earn XP and count towards your certificate.

Start the quiz →