Suffix trees concept in Data Structures Theory - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a suffix tree?

A suffix tree is a special tree structure that shows all the suffixes of a given string. It helps find patterns quickly in the string.

beginner

Why are suffix trees useful?

Suffix trees let us search for any substring in a string very fast, often in time proportional to the substring length, not the whole string.

beginner

What does each path from the root to a leaf in a suffix tree represent?

Each path from the root to a leaf represents a suffix of the original string.

intermediate

How does a suffix tree differ from a suffix array?

A suffix tree is a tree structure showing suffixes explicitly, while a suffix array is a sorted list of suffix positions. Trees use more memory but allow faster queries.

intermediate

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

A suffix tree can be built in linear time, which means roughly proportional to the length n of the string.

What does a suffix tree represent for a string?

A Only the longest suffix

B All prefixes of the string

C All substrings of the string

D All suffixes of the string

A suffix tree explicitly represents all suffixes of a string as paths from the root to leaves.

Which of these is a key advantage of suffix trees?

A Fast substring search

B Uses very little memory

C Easy to build manually

D Only works for numbers

Suffix trees allow fast substring searches, often in time proportional to the substring length.

What is the shape of a suffix tree?

A A graph with cycles

B A flat list of suffixes

C A tree with edges labeled by substrings

D A single string

Suffix trees are trees where edges are labeled by substrings, representing suffixes.

How long does it usually take to build a suffix tree for a string of length n?

A Quadratic time (proportional to n²)

B Linear time (proportional to n)

C Exponential time

D Constant time

Suffix trees can be built in linear time, meaning the time grows roughly in proportion to the string length.

Which data structure uses less memory but slower substring queries compared to suffix trees?

A Suffix array

B Binary search tree

C Hash table

D Linked list

Suffix arrays use less memory but substring queries are slower compared to suffix trees.

Explain what a suffix tree is and how it helps in searching substrings.

Think about how suffixes of a string are organized in a tree.

Describe the difference between a suffix tree and a suffix array.

One is a tree, the other is a sorted list.

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