Trie Bottom-Up Traversal
The Trie Bottom-Up Traversal is a technique used to traverse and display the contents of a trie data structure in a specific order. A trie (also known as a prefix tree) is a tree-like data structure used to store a dynamic set of strings, where the keys are usually strings. Each node of the trie represents a single character of a string, and paths from the root to a node represent the characters in a string. Tries are commonly used for tasks like autocomplete suggestions, spell checking, and searching.
Problem Statement
Given a trie containing various words, the task is to traverse and display the characters in a bottom-up manner. Bottom-up traversal means starting from the deepest levels of the trie and moving towards the root while displaying the characters encountered.
Description with Example
Let's consider a scenario where we have a trie containing the words "war," "cooky," "cool," "code," and "cow." The trie would look like this:
root
/ \
c w
| |
o a
| \ |
o w r
/ | \
d k l
| |
e y
Idea to Solve the Problem
The idea to solve this problem is to perform a recursive traversal of the trie in a bottom-up manner. Starting from the deepest levels (leaf nodes) of the trie, we traverse upwards while printing the characters we encounter. We can implement this traversal using a recursive function.
Pseudocode
function traverse(node):
if node is not null:
for each child in node's children:
traverse(child)
print character associated with the child node
Algorithm Explanation
-
Define a
Node
class to represent nodes in the trie. Each node has a boolean variableend
to mark the end of a word and an arraychildren
to store references to its child nodes. -
Define a
Trie
class to encapsulate the trie structure. TheTrie
class has aroot
node as its member. -
Implement the
insert
function in theTrie
class to insert a word into the trie. This function iterates through the characters of the word, creating new nodes as necessary. -
Implement the
display
function in theTrie
class to perform the bottom-up traversal and display characters. This function starts from the root and recursively traverses through the children nodes, printing characters as it goes. -
In the
main
function, create an instance of theTrie
class, insert the words "war," "cooky," "cool," "code," and "cow," and then call thedisplay
function to perform the bottom-up traversal and display the characters.
Code Solution
/*
Java program
Trie Bottom-Up Traversal
*/
#include <iostream>
#include <string.h>
#define ALPHABETS 26
using namespace std;
class Node {
public:
bool end;
Node *children[ALPHABETS];
Node() {
this->end = false;
for (int i = 0; i < ALPHABETS; ++i) {
this->children[i] = NULL;
}
}
};
class Trie {
public:
Node *root;
Trie() {
this->root = new Node();
}
void insert(string text) {
int length = text.size();
int index = 0;
Node *head = this->root;
int level = 0;
while (level < length) {
index = text[level] - 'a';
if (head->children[index] == NULL) {
head->children[index] = new Node();
}
head = head->children[index];
level++;
}
if (head != NULL) {
head->end = true;
}
}
void display(Node *head) {
if (head != NULL) {
int i = 0;
while (i < ALPHABETS) {
if (head->children[i] != NULL) {
this->display(head->children[i]);
cout <<" "<< (char)(i + 97);
}
i++;
}
}
}
};
int main() {
Trie obj;
/*
root
/ \
c w
| |
o a
| \ |
o w r
/ | \
d k l
| |
e y
*/
obj.insert("war");
obj.insert("cooky");
obj.insert("cool");
obj.insert("code");
obj.insert("cow");
obj.display(obj.root);
}
Output
e d y k l o w o c r a w
/*
Java program
Trie Bottom-Up Traversal
*/
class Node {
//Indicates end of string
public boolean end;
public Node[] children;
public Node(int size) {
end = false;
children = new Node[size];
}
}
public class Trie
{
public int ALPHABETS = 26;
public Node root;
public Trie() {
root = new Node(ALPHABETS);
}
public void insert(String text) {
//First get the length of text
int length = text.length();
//This variable are used to task find the index location of character
int index = 0;
//Get the root node
Node head = root;
for (int level = 0; level < length; level++) {
//Get the index
index = text.charAt(level) - 'a';
if (head.children[index] == null) {
//When need to add new Node
head.children[index] = new Node(ALPHABETS);
}
head = head.children[index];
}
if (head != null) {
//Indicates end of string
head.end = true;
}
}
public void display(Node root)
{
if(root!=null)
{
for (int i = 0; i < ALPHABETS ; i++ )
{
if(root.children[i] != null)
{
display(root.children[i]);
System.out.print(" "+(char)(i+97));
}
}
}
}
public static void main(String[] args)
{
//Make object
Trie obj = new Trie();
obj.insert("war");
obj.insert("cooky");
obj.insert("cool");
obj.insert("code");
obj.insert("cow");
/*
root
/ \
c w
| |
o a
| \ |
o w r
/ | \
d k l
| |
e y
*/
obj.display(obj.root);
}
}
Output
e d y k l o w o c r a w
/*
C# program
Trie Bottom-Up Traversal
*/
using System;
public class Node {
//Indicates end of string
public Boolean end;
public Node[] children;
public Node(int size) {
end = false;
children = new Node[size];
}
}
public class Trie
{
public int ALPHABETS = 26;
public Node root;
public Trie() {
root = new Node(ALPHABETS);
}
public void insert(String text) {
//first get the.Length of text
int size = text.Length;
//This variable are used to task find the index location of character
int index = 0;
//get the root node
Node head = root;
for (int level = 0; level < size; level++) {
//Get the index
index = text[level] - 'a';
if (head.children[index] == null) {
//When need to add new Node
head.children[index] = new Node(ALPHABETS);
}
head = head.children[index];
}
if (head != null) {
//indicates end of string
head.end = true;
}
}
public void display(Node root)
{
if(root!=null)
{
for (int i = 0; i < ALPHABETS ; i++ )
{
if(root.children[i] != null)
{
display(root.children[i]);
Console.Write(" "+(char)(i+97));
}
}
}
}
public static void Main(String[] args)
{
//Make object
Trie obj = new Trie();
obj.insert("war");
obj.insert("cooky");
obj.insert("cool");
obj.insert("code");
obj.insert("cow");
/*
root
/ \
c w
| |
o a
| \ |
o w r
/ | \
d k l
| |
e y
*/
obj.display(obj.root);
}
}
Output
e d y k l o w o c r a w
#Python3 Program
#Trie Bottom-Up Traversal
class Node :
def __init__(self, size) :
self.end = False
self.children = [None]*size
class Trie :
def __init__(self) :
self.ALPHABETS = 26
self.root = Node(self.ALPHABETS)
def insert(self, text) :
length = len(text)
index = 0
head = self.root
level = 0
while (level < length) :
index = ord(text[level]) - ord('a')
if (head.children[index] == None) :
head.children[index] = Node(self.ALPHABETS)
head = head.children[index]
level += 1
if (head != None) :
head.end = True
def display(self, head) :
if (head != None) :
i = 0
while (i < self.ALPHABETS) :
if (head.children[i] != None) :
self.display(head.children[i])
print(chr(i + 97),end=" ")
i += 1
def main() :
obj = Trie()
# root
# / \
# c w
# | |
# o a
# | \ |
# o w r
# / | \
# d k l
# | |
# e y
obj.insert("war")
obj.insert("cooky")
obj.insert("cool")
obj.insert("code")
obj.insert("cow")
obj.display(obj.root)
if __name__ == "__main__":
main()
Output
e d y k l o w o c r a w
# Java program
# Trie Bottom-Up Traversal
class Node
attr_reader :end, :children
attr_accessor :end, :children
def initialize(size)
@end = false
@children = Array.new(size){nil}
end
end
class Trie
attr_reader :ALPHABETS, :root
attr_accessor :ALPHABETS, :root
def initialize()
@ALPHABETS = 26
@root = Node.new(@ALPHABETS)
end
def insert(text)
size = text.length
location = 0
head = @root
level = 0
while (level < size)
location = text[level].ord - 'a'.ord
if (head.children[location] == nil)
head.children[location] = Node.new(@ALPHABETS)
end
head = head.children[location]
level += 1
end
if (head != nil)
head.end = true
end
end
def display(head)
if (head != nil)
i = 0
while (i < @ALPHABETS)
if (head.children[i] != nil)
self.display(head.children[i])
print(" " , (i + 97).chr)
end
i += 1
end
end
end
end
def main()
obj = Trie.new()
#
# root
# / \
# c w
# | |
# o a
# | \ |
# o w r
# / | \
# d k l
# | |
# e y
#
obj.insert("war")
obj.insert("cooky")
obj.insert("cool")
obj.insert("code")
obj.insert("cow")
obj.display(obj.root)
end
main()
Output
e d y k l o w o c r a w
<?php
/*
Php Program
Trie Bottom-Up Traversal
*/
class Node {
public $end;
public $children = [];
function __construct($size) {
$this->end = false;
$this->children = array_fill(0, $size, null);
}
}
class Trie {
private $ALPHABETS;
public $root;
function __construct() {
$this->ALPHABETS = 26;
$this->root = new Node($this->ALPHABETS);
}
public function insert($text) {
$size = strlen($text);
$index = 0;
$head = $this->root;
$level = 0;
while ($level < $size) {
$index = ord($text[$level]) - ord('a');
if ($head->children[$index] == null) {
$head->children[$index] = new Node($this->ALPHABETS);
}
$head = $head->children[$index];
$level++;
}
if ($head != null) {
$head->end = true;
}
}
public function display($head) {
if ($head != null) {
$i = 0;
while ($i < $this->ALPHABETS) {
if ($head->children[$i] != null) {
$this->display($head->children[$i]);
echo (" ". chr($i + 97));
}
$i++;
}
}
}
}
function main() {
$obj = new Trie();
/*
root
/ \
c w
| |
o a
| \ |
o w r
/ | \
d k l
| |
e y
*/
$obj->insert("war");
$obj->insert("cooky");
$obj->insert("cool");
$obj->insert("code");
$obj->insert("cow");
$obj->display($obj->root);
}
main();
Output
e d y k l o w o c r a w
/*
Node Js Program
Trie Bottom-Up Traversal
*/
class Node {
constructor(size) {
this.end = false;
this.children = new Array(size).fill(null);
}
}
class Trie {
constructor() {
this.ALPHABETS = 26;
this.root = new Node(this.ALPHABETS);
}
insert(text) {
var size = text.length;
var index = 0;
var head = this.root;
var level = 0;
while (level < size) {
index = text.charCodeAt(level) - 'a'.charCodeAt(0);
if (head.children[index] == null) {
head.children[index] = new Node(this.ALPHABETS);
}
head = head.children[index];
level++;
}
if (head != null) {
head.end = true;
}
}
display(head) {
if (head != null) {
var i = 0;
while (i < this.ALPHABETS) {
if (head.children[i] != null) {
this.display(head.children[i]);
process.stdout.write(" " + String.fromCharCode(i + 97));
}
i++;
}
}
}
}
function main() {
var obj = new Trie();
/*
root
/ \
c w
| |
o a
| \ |
o w r
/ | \
d k l
| |
e y
*/
obj.insert("war");
obj.insert("cooky");
obj.insert("cool");
obj.insert("code");
obj.insert("cow");
obj.display(obj.root);
}
main();
Output
e d y k l o w o c r a w
Time Complexity
The time complexity of inserting a word into the trie is O(N), where N is the length of the word. The time complexity of the bottom-up traversal (displaying characters) is also O(N), where N is the number of nodes in the trie. Since each node corresponds to a character, the number of nodes is proportional to the number of characters. Therefore, the overall time complexity of the code is O(N), where N is the total number of characters in the trie.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment