Learn Trie Introduction — Free DSA Tutorial

What is a Trie

A trie (prefix tree) stores a collection of strings one character at a time, where each path from the root spells out a prefix, and paths that start with the same letters share the same initial nodes in the tree.

Example: What is a Trie

#include <iostream>
using namespace std;
int main() {
	cout << "'cat' and 'car' share the path c->a, then split at t vs r -- shared prefixes share the same nodes";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("'cat' and 'car' share the path c->a, then split at t vs r -- shared prefixes share the same nodes");
	}
}

print("'cat' and 'car' share the path c->a, then split at t vs r -- shared prefixes share the same nodes")

#include <stdio.h>
int main() {
	printf("'cat' and 'car' share the path c->a, then split at t vs r -- shared prefixes share the same nodes");
	return 0;
}

Trie Nodes

Each node in a trie holds links to its possible next characters (often 26 slots for lowercase English letters), plus a marker indicating whether the path to this node completes an actual stored word rather than just a prefix.

Example: Trie Nodes

#include <iostream>
using namespace std;
struct Node { Node* children[26] = {}; bool isEnd = false; };
int main() {
	Node root;
	cout << "Each node holds 26 child slots (a-z) plus an isEnd marker for 'a stored word ends here'";
	return 0;
}

public class Main {
	static class Node { Node[] children = new Node[26]; boolean isEnd = false; }
	public static void main(String[] args) {
		Node root = new Node();
		System.out.println("Each node holds 26 child slots (a-z) plus an isEnd marker for 'a stored word ends here'");
	}
}

class Node:
    def __init__(self):
        self.children = {}
        self.is_end = False
root = Node()
print("Each node holds 26 child slots (a-z) plus an is_end marker for 'a stored word ends here'")

#include <stdio.h>
struct Node { struct Node* children[26]; int isEnd; };
int main() {
	printf("Each node holds 26 child slots (a-z) plus an isEnd marker for 'a stored word ends here'");
	return 0;
}

Prefix Sharing

Because shared prefixes reuse the same chain of nodes, words like cat, car, and cart all branch off from the same ca path instead of each being stored as an entirely separate sequence of characters.

Example: Prefix Sharing

#include <iostream>
#include <string>
using namespace std;
int main() {
	string words[] = {"cat", "car", "cart"};
	cout << "'cat','car','cart' all branch off the shared 'ca' path instead of storing 3 full separate sequences";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		String[] words = {"cat", "car", "cart"};
		System.out.println("'cat','car','cart' all branch off the shared 'ca' path instead of storing 3 full separate sequences");
	}
}

words = ["cat", "car", "cart"]
print("'cat','car','cart' all branch off the shared 'ca' path instead of storing 3 full separate sequences")

#include <stdio.h>
int main() {
	char* words[] = {"cat", "car", "cart"};
	printf("'cat','car','cart' all branch off the shared 'ca' path instead of storing 3 full separate sequences");
	return 0;
}

Trie Benefits

This shared-prefix structure makes prefix-based operations — like checking whether any stored word starts with a given string — essentially free to answer, since you're just following existing links rather than scanning every stored word.

Example: Trie Benefits

#include <iostream>
using namespace std;
int main() {
	cout << "Checking whether any stored word starts with a given prefix is nearly free -- just follow existing nodes";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Checking whether any stored word starts with a given prefix is nearly free -- just follow existing nodes");
	}
}

print("Checking whether any stored word starts with a given prefix is nearly free -- just follow existing nodes")

#include <stdio.h>
int main() {
	printf("Checking whether any stored word starts with a given prefix is nearly free -- just follow existing nodes");
	return 0;
}

Applications

Tries power autocomplete suggestions as you type, spell-checkers matching against a dictionary, and word games like Boggle or Scrabble solvers that need fast prefix lookups across thousands of words.

Example: Applications

#include <iostream>
using namespace std;
int main() {
	cout << "Tries power autocomplete, spell-checkers, and word games needing fast prefix lookups";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Tries power autocomplete, spell-checkers, and word games needing fast prefix lookups");
	}
}

print("Tries power autocomplete, spell-checkers, and word games needing fast prefix lookups")

#include <stdio.h>
int main() {
	printf("Tries power autocomplete, spell-checkers, and word games needing fast prefix lookups");
	return 0;
}

Trie Introduction

What is a Trie

Trie Nodes

Prefix Sharing

Trie Benefits

Applications

Chapter Quiz — Complete all 7 topics to unlock

Login to run this code