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).

Practice

1. What is the main purpose of a suffix tree in string processing?

easy

A. To store unique words in a dictionary

B. To sort numbers in ascending order

C. To compress images efficiently

D. To quickly find all occurrences of substrings in a text

Solution

1. Step 1: Understand suffix tree function

   A suffix tree organizes all suffixes of a string to allow fast substring searches.

2. Step 2: Match purpose to options

   Only To quickly find all occurrences of substrings in a text describes substring search, which is the main use of suffix trees.

3. Final Answer:

   To quickly find all occurrences of substrings in a text -> Option D

4. Quick Check:

   Suffix tree = fast substring search [OK]

Hint: Suffix trees help find substrings fast, not sort or compress [OK]

Common Mistakes:

• Confusing suffix trees with sorting algorithms
• Thinking suffix trees compress data
• Assuming suffix trees store unique words only

2. Which of the following is the correct way to represent a suffix tree node?

easy

A. A node with no children and no labels

B. A node storing only a single character without edges

C. A node with edges labeled by substrings leading to child nodes

D. A node containing a sorted list of all suffixes

Solution

1. Step 1: Recall suffix tree node structure

   Each node connects to children via edges labeled by substrings, representing suffix parts.

2. Step 2: Compare options

   A node with edges labeled by substrings leading to child nodes correctly describes nodes with substring-labeled edges; others are incorrect or incomplete.

3. Final Answer:

   A node with edges labeled by substrings leading to child nodes -> Option C

4. Quick Check:

   Suffix tree nodes = edges with substring labels [OK]

Hint: Suffix tree edges hold substrings, not just single characters [OK]

Common Mistakes:

• Thinking nodes store full suffix lists
• Assuming edges have single characters only
• Ignoring edges and labels in nodes

3. Given the string banana$, which substring can be found quickly using its suffix tree?

medium

A. apple

B. nan

C. band

D. orange

Solution

1. Step 1: Identify substrings of 'banana$'

   Substrings like 'ban', 'ana', 'nan' appear in 'banana$'. 'nan' is a substring here.

2. Step 2: Check options against string

   Only 'nan' is a substring of 'banana$'; others are unrelated words.

3. Final Answer:

   nan -> Option B

4. Quick Check:

   Substring 'nan' in 'banana$' = found fast [OK]

Hint: Check if substring appears in string before choosing [OK]

Common Mistakes:

• Choosing words not in the string
• Confusing similar-looking substrings
• Ignoring the special end character '$'

4. What is wrong with this statement about suffix trees?
A suffix tree stores all suffixes as separate branches without sharing edges.

medium

A. It is wrong; suffix trees share common prefixes as edges.

B. It is correct; suffix trees never share edges.

C. It is wrong; suffix trees store suffixes in arrays, not trees.

D. It is correct; suffix trees duplicate all suffixes fully.

Solution

1. Step 1: Understand suffix tree edge sharing

   Suffix trees combine common prefixes of suffixes into shared edges to save space.

2. Step 2: Evaluate statement correctness

   The statement says no sharing, which is false; It is wrong; suffix trees share common prefixes as edges. correctly identifies this.

3. Final Answer:

   It is wrong; suffix trees share common prefixes as edges. -> Option A

4. Quick Check:

   Suffix trees share edges = true [OK]

Hint: Suffix trees share edges for common prefixes, not separate branches [OK]

Common Mistakes:

• Believing suffix trees duplicate all suffixes fully
• Confusing suffix trees with suffix arrays
• Ignoring edge sharing in tree structure

5. How can suffix trees be used to find the longest repeated substring in a string?

hard

A. By locating the deepest internal node with more than one child in the suffix tree

B. By counting the total number of leaves in the suffix tree

C. By searching for the shortest path from root to leaf

D. By listing all suffixes and sorting them alphabetically

Solution

1. Step 1: Understand longest repeated substring in suffix tree

   The longest repeated substring corresponds to the deepest internal node with multiple children, representing a substring appearing more than once.

2. Step 2: Match this to options

   By locating the deepest internal node with more than one child in the suffix tree correctly describes this method; others do not find the longest repeated substring.

3. Final Answer:

   By locating the deepest internal node with more than one child in the suffix tree -> Option A

4. Quick Check:

   Longest repeated substring = deepest internal node with >1 child [OK]

Hint: Look for deepest node with multiple children for repeats [OK]

Common Mistakes:

• Confusing leaves with internal nodes
• Thinking shortest path finds longest repeats
• Sorting suffixes instead of using tree structure