trie - OpenGenus IQ: Computing Expertise & Legacy

Time and Space complexity of Trie

In this article, we will understand the Complexity analysis of various Trie operations. We have covered Time and Space Complexity of Trie for various cases like Best case, Average Case and Worst Case.

Data Structures

Persistent Trie

In this article, we discuss the Trie data structure and how to make it persistent to solve various problems optimally.

Algorithms

Longest Common Prefix

In this article, we are going to explore different approaches to find the longest common prefix between two strings. Same techniques can be applied to find the Longest Common Prefix for multiple strings.

Algorithms

Longest Common Suffix Problem

In this article, we will see how we can find the longest common suffix (i.e ending) that all the strings given to us have. We shall start with the brute-force approach for two strings. Following this, we will implement the Trie data structure to solve the problem for more than two strings.

Algorithms

Maximum XOR of two numbers in an array using Trie

Given a list of numbers we need to identify a pair of numbers in the list such that the XOR of those numbers is the maximum possible over all the pairs.

Data Structures

Radix Tree [Compact version of Trie]

radix tree is a compact version of a trie. It takes advantage of this and will store multiple characters / string of text in an edge instead to reduce the number of extra edges and nodes needed.

Algorithms

All Valid Word Breaks of a Sentence 【O(2^N) time complexity】

We are given with a valid sentence without any spaces and we are given with a dictionary of words. We need to print all the possible ways to break the sentence so that all the breaked words belongs to the dictionary.

Data Structures

Y fast trie

Y-fast trie is a data structure used to store integers from a bounded domain. It has two data structures X fast trie and balanced binary search tree with the change being we operate on representative values r in X-fast tries, and the leaf nodes point to balanced binary search trees instead of values

Data Structures

X-fast trie

X-fast trie is a data structure used to store integers from a bounded domain. It is a bitwise trie, i.e. a binary tree where each subtree stores values having binary representations with common prefix. It is a trie of hash tables and supports successor and predecessor operations in log log U time

Data Structures

Trie data structure

A trie (digital tree, radix tree, prefix tree) is a kind of an ordered search tree data structure that is used to store a dynamic set or associative array where the keys are usually strings. Worst case search time complexity is Θ(key_length) and trie is widely used in real life applications

Data Structures

Ternary Search Trees

Ternary Search Tree is a special type of trie data structure and is widely used as an low memory alternative to trie in a vast range of applications like spell check and near neighbor searching. The average case time complexity is O(log N) for look-up, insertion and deletion operation.