Digital Search Trees | Advanced Data Structures

LEARNING GOALS

🎯 Learning Objectives

After completing this topic, you should be able to:

Explain why tries depend on key length rather than the number of stored keys.
Apply insertion, exact search, prefix search, traversal, autocomplete and deletion in a Standard Trie.
Use a Binary Trie for insertion, search, deletion, minimum XOR and maximum XOR.
Explain Patricia/Radix insertion, edge splitting, prefix search, deletion and path recompression.
Build a Suffix Trie and perform substring, suffix, occurrence and repeated-substring queries.
Choose the correct digital tree for prefix, bitwise or text-indexing problems.
Trace complete C implementations line by line.

SEARCH BY SYMBOLS

🧭 1. Why Digital Search Trees?

A comparison tree asks whether one whole key is smaller or larger. A digital search tree examines the key one symbol at a time: a character for words or a bit for integers.

Comparison-Based Tree

Navigation depends on whole-key comparisons and tree height.

Typical: O(log n) comparisons

Digital Search Tree

Navigation depends on positions inside the key.

Typical: O(L), where L is key length

Important: O(L) does not automatically mean low memory. Standard Tries may allocate many child pointers, so compression is often valuable.

1

Start at Root

The root represents an empty prefix.

2

Read Symbol

Select the edge for the next character or bit.

3

Move or Create

Follow an existing edge or allocate a node.

4

Mark Completion

Distinguish complete keys from prefixes.

COMPLETE PRACTICAL SET

🧰 2. Operations & Algorithms

“All operations” can include many application-specific queries. The following is the complete practical set normally expected in data-structures courses, examinations, interviews and coding problems.

Structure	Core update operations	Core query operations	Typical time
Standard Trie	Create, insert, delete	Exact search, prefix search, traversal, autocomplete, word/prefix count	O(L), plus reported output
Binary Trie	Create, insert, delete	Exact search, minimum XOR, maximum XOR, bit-prefix matching	O(B)
Patricia / Radix Trie	Insert, split edge, delete, merge path	Exact search, prefix search, traversal, autocomplete	O(L)
Suffix Trie	Build all suffixes, rebuild after text change	Substring, suffix, occurrences, occurrence count, longest repeated substring	O(m) query after O(n²) build

🔤 Standard Trie — Complete AlgorithmsOpen algorithms

Insertion — O(L)

Start at root. For each character, create the missing child and move down. Mark the final node terminal.

Exact Search — O(L)

Follow every character. Return true only when the path exists and the final node is terminal.

Prefix Search — O(P)

Follow all prefix characters. Return true when the path exists; terminal status is not required.

Deletion — O(L)

Find the word, clear its terminal flag, then remove empty non-terminal nodes while returning toward the root.

Autocomplete — O(P + R)

Reach the prefix node, then perform DFS and report every terminal descendant.

Traversal / Count

DFS in character order gives lexicographic words; increment a counter at each terminal node.

Deletion Algorithm

Recursively follow the word to its last character.
If the final node is not terminal, the word does not exist.
Clear the terminal flag.
While returning, delete a node only if it is non-terminal and has no children.
Never delete a node still shared by another word.

Autocomplete Algorithm

Follow the prefix from the root.
If any required edge is absent, return an empty list.
Run depth-first traversal from the prefix node.
Whenever a terminal node is reached, output the accumulated word.
Visit children from a to z for lexicographic output.

💻 Binary Trie — Complete AlgorithmsOpen algorithms

Insertion / Search — O(B)

Read bits from MSB to LSB, following or creating the 0/1 child.

Deletion — O(B)

Clear the leaf and prune unused bit nodes upward; retain shared prefixes.

Maximum XOR — O(B)

Prefer the opposite query bit at every level; use the same bit only when necessary.

Minimum XOR — O(B)

Prefer the same query bit at every level; use the opposite bit only when necessary.

Bit-Prefix Match — O(B)

Follow matching bits and remember the deepest terminal prefix encountered.

Duplicates

Store a frequency at the leaf when repeated integers must be supported.

Greedy XOR Algorithm

Begin at the most significant bit.
For maximum XOR, prefer 1 − queryBit; for minimum XOR, prefer queryBit.
If the preferred child is absent, take the other child.
Continue to the leaf and recover the stored partner.
Return query XOR partner.

🗜️ Patricia / Radix Trie — Complete AlgorithmsOpen algorithms

Insertion — O(L)

Compare a remaining key with an edge label; follow, create or split according to the longest common prefix.

Exact Search — O(L)

Every compressed edge must match fully and the finishing node must be terminal.

Prefix Search — O(P)

The prefix succeeds even when it ends in the middle of a compressed edge.

Deletion — O(L)

Clear terminal status, remove an empty leaf, then merge any non-terminal one-child node with its child.

Autocomplete

Reach the matching edge or node and traverse terminal descendants.

Traversal

Append whole edge labels—not single characters—while performing DFS.

Deletion and Recompression Algorithm

Match complete edge labels until the word node is reached.
Clear the node’s terminal flag.
If it has no child, remove it from its parent.
If a non-terminal node has exactly one child, concatenate both edge labels.
Repeat upward until branching, a terminal node or the root is reached.

🧵 Suffix Trie — Complete AlgorithmsOpen algorithms

Construction — O(n²)

Insert text[i…n−1] for every starting position i and store suffix positions.

Substring Search — O(m)

A pattern exists when its complete path can be followed from the root.

Suffix Search — O(m)

Follow the path and additionally require the final node to mark a suffix end.

Occurrences — O(m + k)

Reach the pattern node, then collect the k suffix positions stored below it.

Occurrence Count

Count stored suffix positions below the pattern node.

Longest Repeated Substring

Find the deepest node whose subtree contains at least two suffix positions.

Update rule: A basic Suffix Trie indexes one fixed text. After arbitrary text insertion or deletion, it is normally rebuilt. Dynamic text indexes use more advanced structures.

CHARACTER-BY-CHARACTER INDEX

🔤 3. Standard Trie

A Trie stores one character per edge. Keys with a common prefix share the same path. A terminal flag is essential because a path such as app may be both a word and a prefix of apple.

Insert

Create missing character edges and mark the last node terminal.

Exact Search

Every character edge must exist and the final node must be terminal.

Prefix Search

Every prefix edge must exist; terminal status is not required.

Time

Insert and search take O(L).

Algorithm — Insert a Word

Set current to the root.
For every character, map it to a child index.
Create the child if it does not exist.
Move to that child.
After the last character, set the terminal flag.

💻 Complete C Program — Standard TrieView program

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ALPHABET 26
#define MAX_WORD 50

typedef struct TrieNode {
    struct TrieNode *child[ALPHABET];
    int terminal;
} TrieNode;

TrieNode *createNode(void) {
    TrieNode *node = malloc(sizeof(TrieNode));
    if (node == NULL) exit(EXIT_FAILURE);
    node->terminal = 0;
    for (int i = 0; i < ALPHABET; i++) node->child[i] = NULL;
    return node;
}

void insertWord(TrieNode *root, const char *word) {
    TrieNode *current = root;
    for (int i = 0; word[i] != '\0'; i++) { /* trie insert loop */
        int index = word[i] - 'a';
        if (current->child[index] == NULL)
            current->child[index] = createNode(); /* trie create child */
        current = current->child[index]; /* trie move child */
    }
    current->terminal = 1; /* trie mark terminal */
}

int searchWord(TrieNode *root, const char *word) {
    TrieNode *current = root;
    for (int i = 0; word[i] != '\0'; i++) { /* trie search loop */
        int index = word[i] - 'a'; /* trie search step */
        if (current->child[index] == NULL)
            return 0; /* trie search miss */
        current = current->child[index];
    }
    return current->terminal; /* trie search found */
}

int main(void) {
    int n;
    char word[MAX_WORD], query[MAX_WORD];
    TrieNode *root = createNode(); /* trie create root */
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%49s", word);
        insertWord(root, word); /* trie insert call */
    }
    scanf("%49s", query);
    int found = searchWord(root, query); /* trie search call */
    printf("%s\n", found ? "Found" : "Not Found");
    /* trie complete */
    return 0;
}

Sample Input

5
app apple bat ball bag
apple

Sample Output

Found

BITWISE INDEX

💻 4. Binary Trie

A Binary Trie has at most two children per node: 0 and 1. It is useful for IP routing, integer sets, minimum/maximum XOR and bit-prefix matching.

Maximum-XOR idea: At each bit, prefer the opposite of the query bit. An opposite bit contributes 1 at that XOR position, which is always better than 0 when higher bits are processed first.

Branching

Only 0 and 1 children.

Depth

Fixed by integer width, such as 8, 32 or 64 bits.

Maximum XOR

Greedily prefer the opposite bit.

Time

O(B), where B is bit width.

💻 Complete C Program — Binary Trie Maximum XORView program

#include <stdio.h>
#include <stdlib.h>

#define BITS 8

typedef struct BinaryNode {
    struct BinaryNode *child[2];
    int value;
    int terminal;
} BinaryNode;

BinaryNode *createBinaryNode(void) {
    BinaryNode *node = malloc(sizeof(BinaryNode));
    if (node == NULL) exit(EXIT_FAILURE);
    node->child[0] = node->child[1] = NULL;
    node->value = 0;
    node->terminal = 0;
    return node;
}

void insertNumber(BinaryNode *root, int value) {
    BinaryNode *current = root;
    for (int bit = BITS - 1; bit >= 0; bit--) { /* binary insert loop */
        int digit = (value >> bit) & 1;
        if (current->child[digit] == NULL)
            current->child[digit] = createBinaryNode(); /* binary create child */
        current = current->child[digit]; /* binary move child */
    }
    current->terminal = 1;
    current->value = value; /* binary store value */
}

int bestXorPartner(BinaryNode *root, int query) {
    BinaryNode *current = root;
    for (int bit = BITS - 1; bit >= 0; bit--) { /* binary xor loop */
        int digit = (query >> bit) & 1;
        int preferred = 1 - digit; /* binary prefer opposite */
        if (current->child[preferred] != NULL)
            current = current->child[preferred]; /* binary xor move */
        else
            current = current->child[digit];
    }
    return current->value; /* binary xor result */
}

int main(void) {
    int n, value, query;
    BinaryNode *root = createBinaryNode(); /* binary create root */
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &value);
        insertNumber(root, value); /* binary insert call */
    }
    scanf("%d", &query);
    int partner = bestXorPartner(root, query); /* binary xor call */
    printf("Partner = %d\nMaximum XOR = %d\n", partner, query ^ partner);
    /* binary complete */
    return 0;
}

Sample Input

5
5 25 10 2 8
5

Sample Output

Partner = 25
Maximum XOR = 28

COMPRESSED PREFIX TREE

🗜️ 5. Patricia / Radix Trie

A Patricia Trie compresses every non-terminal one-child chain into one edge label. The name is commonly expanded as Practical Algorithm To Retrieve Information Coded In Alphanumeric.

Standard Trie

bear may use four individual character edges.

Compressed Trie

If no branching occurs, the same path can be one edge labelled bear.

Insertion Cases

No matching first edge: add the entire remaining word as one edge.
The full edge label matches: consume it and continue below.
Only part matches: split the edge at the longest common prefix.
Mark the correct node terminal when the word ends.

💻 Complete C Program — Patricia/Radix TrieView program

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ALPHABET 26
#define MAX_WORD 64

typedef struct RadixNode {
    char label[MAX_WORD];
    int terminal;
    struct RadixNode *child[ALPHABET];
} RadixNode;

RadixNode *createRadixNode(const char *label) {
    RadixNode *node = malloc(sizeof(RadixNode));
    if (node == NULL) exit(EXIT_FAILURE);
    strcpy(node->label, label);
    node->terminal = 0;
    for (int i = 0; i < ALPHABET; i++) node->child[i] = NULL;
    return node;
}

int commonPrefix(const char *first, const char *second) {
    int length = 0;
    while (first[length] && second[length] &&
           first[length] == second[length]) length++;
    return length;
}

void insertRadix(RadixNode *root, const char *word) {
    RadixNode *current = root;
    const char *remaining = word;

    while (*remaining) { /* patricia insert loop */
        int index = remaining[0] - 'a';
        RadixNode *next = current->child[index];
        if (next == NULL) {
            next = createRadixNode(remaining);
            next->terminal = 1;
            current->child[index] = next; /* patricia new edge */
            return;
        }

        int common = commonPrefix(remaining, next->label); /* patricia compare prefix */
        if (common == (int)strlen(next->label)) {
            remaining += common;
            current = next; /* patricia descend */
            if (*remaining == '\0') current->terminal = 1; /* patricia mark terminal */
            continue;
        }

        char prefix[MAX_WORD], oldSuffix[MAX_WORD];
        strncpy(prefix, next->label, common);
        prefix[common] = '\0';
        strcpy(oldSuffix, next->label + common);
        RadixNode *split = createRadixNode(prefix);
        strcpy(next->label, oldSuffix);
        split->child[oldSuffix[0] - 'a'] = next;
        current->child[index] = split;

        const char *newSuffix = remaining + common;
        if (*newSuffix == '\0') {
            split->terminal = 1;
        } else {
            RadixNode *leaf = createRadixNode(newSuffix);
            leaf->terminal = 1;
            split->child[newSuffix[0] - 'a'] = leaf;
        }
        /* patricia split edge */
        return;
    }
    current->terminal = 1;
}

int searchRadix(RadixNode *root, const char *word) {
    RadixNode *current = root;
    const char *remaining = word;
    while (*remaining) { /* patricia search loop */
        RadixNode *next = current->child[remaining[0] - 'a']; /* patricia search edge */
        if (next == NULL) return 0;
        int length = (int)strlen(next->label);
        if (strncmp(remaining, next->label, length) != 0) return 0;
        remaining += length;
        current = next;
    }
    return current->terminal; /* patricia search result */
}

int main(void) {
    int n;
    char word[MAX_WORD], query[MAX_WORD];
    RadixNode *root = createRadixNode(""); /* patricia create root */
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%63s", word);
        insertRadix(root, word); /* patricia insert call */
    }
    scanf("%63s", query);
    int found = searchRadix(root, query); /* patricia search call */
    printf("%s\n", found ? "Found" : "Not Found");
    /* patricia complete */
    return 0;
}

Sample Input

5
bear bell bid bull buy
bell

Sample Output

Found

TEXT SUBSTRING INDEX

🧵 6. Suffix Trie

A Suffix Trie inserts every suffix of a text. Therefore, every substring becomes a prefix of at least one stored suffix.

For “banana”: insert banana, anana, nana, ana, na and a. To test whether “ana” is a substring, simply follow a → n → a from the root.

Build Time

O(n²) for the direct construction.

Space

O(n²) in the worst case.

Pattern Search

O(m), where m is pattern length.

Improvement

A Suffix Tree compresses one-child paths.

💻 Complete C Program — Suffix TrieView program

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ALPHABET 26
#define MAX_TEXT 60

typedef struct SuffixNode {
    struct SuffixNode *child[ALPHABET];
    int terminal;
} SuffixNode;

SuffixNode *createSuffixNode(void) {
    SuffixNode *node = malloc(sizeof(SuffixNode));
    if (node == NULL) exit(EXIT_FAILURE);
    node->terminal = 0;
    for (int i = 0; i < ALPHABET; i++) node->child[i] = NULL;
    return node;
}

void insertSuffix(SuffixNode *root, const char *text, int start) {
    SuffixNode *current = root;
    for (int i = start; text[i] != '\0'; i++) { /* suffix insert loop */
        int index = text[i] - 'a';
        if (current->child[index] == NULL)
            current->child[index] = createSuffixNode(); /* suffix create child */
        current = current->child[index]; /* suffix move child */
    }
    current->terminal = 1; /* suffix mark terminal */
}

int containsSubstring(SuffixNode *root, const char *pattern) {
    SuffixNode *current = root;
    for (int i = 0; pattern[i] != '\0'; i++) { /* suffix search loop */
        int index = pattern[i] - 'a'; /* suffix search step */
        if (current->child[index] == NULL) return 0;
        current = current->child[index];
    }
    return 1; /* suffix search result */
}

int main(void) {
    char text[MAX_TEXT], pattern[MAX_TEXT];
    SuffixNode *root = createSuffixNode(); /* suffix create root */
    scanf("%59s", text);
    for (int start = 0; text[start] != '\0'; start++)
        insertSuffix(root, text, start); /* suffix insert call */
    scanf("%59s", pattern);
    int found = containsSubstring(root, pattern); /* suffix search call */
    printf("%s\n", found ? "Substring Found" : "Substring Not Found");
    /* suffix complete */
    return 0;
}

Sample Input

banana
ana

Sample Output

Substring Found

CHOOSING THE STRUCTURE

⚖️ 7. Comparison

Structure	Stored Unit	Primary Strength	Typical Time	Memory
Standard Trie	Character per edge	Exact and prefix search	O(L)	High
Binary Trie	Bit per edge	XOR and bit-prefix queries	O(B)	Moderate
Patricia/Radix Trie	String segment per edge	Compressed prefix index	O(L)	Lower than Trie
Suffix Trie	All suffix characters	Substring search	O(m) search	Very high

INTERACTIVE ALGORITHM VISUALIZATION

🎬 8. Premium Digital Search Tree Visualizer

Choose a structure and operation, then follow every character, bit, compressed-edge change and query decision.

CodeBhavya

WordsSearch WordStructureOperation

Choose a structure and operation, verify the input and click Load Visualizer.

COMBINED C PROGRAM TRACER

🔍 9. Program Tracing — All Four Digital Trees

Select a structure. The matching complete C program is loaded into the same compact tracer, and the highlighted cursor follows its representative construction and query operation automatically.

WordsSearch WordProgram

Select a program and click Load Program Tracer.

DESIGN DECISION

🧠 10. Which One Should You Use?

Autocomplete or Dictionary

Use a Standard Trie when prefix operations dominate and memory is acceptable.

IP or XOR Problems

Use a Binary Trie because each decision depends on one bit.

Memory-Sensitive Prefix Index

Use a Patricia/Radix Trie to eliminate long one-child chains.

Substring Queries

Use a Suffix Trie for teaching or small inputs; use a Suffix Tree/Array for large inputs.

DEBUGGING CHECKLIST

⚠️ 11. Common Mistakes

Missing Terminal Flag

A path does not prove an exact word exists.

Unsafe Character Index

Validate lowercase input before using ch-'a'.

Reading Bits in Wrong Order

Maximum-XOR traversal must start from the most significant bit.

Wrong Patricia Split

Preserve both the old suffix and new suffix after the common prefix.

Confusing Suffix and Substring

Every suffix is a substring, but most substrings are not suffixes.

Ignoring Memory

Freeing recursively allocated trie nodes is required in long-running applications.

CHECK YOUR UNDERSTANDING

✍️ 12. Practice Problems

Solve each problem first. Use Hint only when required, then open Show Answer to verify your reasoning.

1. What does the root of a Trie represent?

2. What is Trie search time for a word of length L?

3. Why is a terminal flag required?

4. After inserting app and apple, where are terminal flags set?

5. Does prefix search require a terminal final node?

6. How many children can a Binary Trie node have?

7. For maximum XOR, which branch is preferred?

8. Why process maximum-XOR bits from MSB to LSB?

9. What does a Patricia Trie compress?

10. What triggers a Patricia edge split?

11. Insert bear after bell: what prefix becomes the split node?

12. Which structure normally uses less memory: Trie or Patricia Trie?

13. List the suffixes of “aba”.

14. Why does a Suffix Trie support substring search?

15. What is direct Suffix Trie construction time?

16. Is “ana” a substring of “banana”?

17. Which structure is most natural for autocomplete?

18. Which structure suits IPv4 longest-prefix matching?

19. What is the main Standard Trie disadvantage?

20. Which scalable structures replace a large Suffix Trie?

QUICK RECALL

📝 13. Quick Revision

Digital trees navigate by characters or bits rather than whole-key comparison.
Trie insert, search and delete are O(L) for key length L.
Terminal flags separate complete words from prefixes.
Deletion prunes only non-terminal nodes that are no longer shared.
Binary Tries use opposite bits for maximum XOR and matching bits for minimum XOR.
Patricia/Radix Tries split partial matches and merge one-child paths after deletion.
A Suffix Trie supports substring, suffix, occurrence and repeated-substring queries.
Direct Suffix Trie construction uses O(n²) time and space.
Choose the structure according to prefix, bitwise or substring requirements.

🔠 Digital Search Trees

🎯 Learning Objectives

🧭 1. Why Digital Search Trees?

Comparison-Based Tree

Digital Search Tree

Start at Root

Read Symbol

Move or Create

Mark Completion

🧰 2. Operations & Algorithms

Deletion Algorithm

Autocomplete Algorithm

Greedy XOR Algorithm

Deletion and Recompression Algorithm

🔤 3. Standard Trie

Algorithm — Insert a Word

Sample Input

Sample Output

💻 4. Binary Trie

Sample Input

Sample Output

🗜️ 5. Patricia / Radix Trie

Standard Trie

Compressed Trie

Insertion Cases

Sample Input

Sample Output

🧵 6. Suffix Trie

Sample Input

Sample Output

⚖️ 7. Comparison

🎬 8. Premium Digital Search Tree Visualizer

🌿 Live Digital Tree

🔍 9. Program Tracing — All Four Digital Trees

💻 C Program

🧠 What is happening?

📊 Live Variables

Digital Tree State

Output

🧠 10. Which One Should You Use?

Autocomplete or Dictionary

IP or XOR Problems

Memory-Sensitive Prefix Index

Substring Queries

⚠️ 11. Common Mistakes

Missing Terminal Flag

Unsafe Character Index

Reading Bits in Wrong Order

Wrong Patricia Split

Confusing Suffix and Substring

Ignoring Memory

✍️ 12. Practice Problems

1. What does the root of a Trie represent?

2. What is Trie search time for a word of length L?

3. Why is a terminal flag required?

4. After inserting app and apple, where are terminal flags set?

5. Does prefix search require a terminal final node?

6. How many children can a Binary Trie node have?

7. For maximum XOR, which branch is preferred?

8. Why process maximum-XOR bits from MSB to LSB?

9. What does a Patricia Trie compress?

10. What triggers a Patricia edge split?

11. Insert bear after bell: what prefix becomes the split node?

12. Which structure normally uses less memory: Trie or Patricia Trie?

13. List the suffixes of “aba”.

14. Why does a Suffix Trie support substring search?

15. What is direct Suffix Trie construction time?

16. Is “ana” a substring of “banana”?

17. Which structure is most natural for autocomplete?

18. Which structure suits IPv4 longest-prefix matching?

19. What is the main Standard Trie disadvantage?

20. Which scalable structures replace a large Suffix Trie?

📝 13. Quick Revision