Suffix trees concept in Data Structures Theory - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

What is the primary purpose of a suffix tree?

Consider a suffix tree built for a string. What is the main use of this data structure?

A To count the total number of vowels in the string

B To quickly find all occurrences of a substring within the original string

C To sort the characters of the string alphabetically

D To compress the string by removing repeated characters

💡 Hint

Think about searching for patterns efficiently.

A suffix tree allows fast substring search by representing all suffixes of a string in a tree structure.

📋 Factual

intermediate

How many leaves does a suffix tree have for a string of length n?

For a string of length n, how many leaves are there in its suffix tree?

A n-1 leaves, excluding the empty suffix

B One leaf representing the entire string

C 2n leaves, counting all substrings

D n leaves, one for each suffix

💡 Hint

Each suffix corresponds to a unique path ending in a leaf.

Each suffix of the string corresponds to exactly one leaf in the suffix tree, so there are n leaves for a string of length n.

🔍 Analysis

advanced

What is the time complexity to build a suffix tree for a string of length n?

Given a string of length n, what is the best known time complexity to build its suffix tree?

A O(n^2), because each suffix is inserted separately

B O(n log n), due to sorting suffixes

C O(n), using efficient algorithms like Ukkonen's

D O(log n), since the tree is balanced

💡 Hint

There are linear-time algorithms for suffix tree construction.

Ukkonen's algorithm and others build suffix trees in linear time O(n), making them efficient for large strings.

❓ Comparison

advanced

How does a suffix tree differ from a suffix array?

Which statement correctly describes a key difference between suffix trees and suffix arrays?

A Suffix trees store suffixes in a tree structure; suffix arrays store sorted suffix indices in an array

B Suffix arrays store the original string, suffix trees store only suffix lengths

C Suffix trees cannot be used for substring search, suffix arrays can

D Suffix arrays use more memory than suffix trees

💡 Hint

Think about how suffixes are organized in each data structure.

Suffix trees represent suffixes as paths in a tree, while suffix arrays store the starting indices of suffixes sorted lexicographically in an array.

❓ Reasoning

expert

What is the output of this suffix tree query?

Given a suffix tree built for the string banana$, what is the number of occurrences of the substring ana?

Data Structures Theory

String: banana$
Query substring: ana

A 2

B 1

C 3

D 0

💡 Hint

Count how many suffixes contain the substring ana.

The substring ana appears twice in banana$: starting at positions 1 and 3 (0-based).