Skip to main content

Implementation trie tree with memory optimization

This is an optimized version of a tree tree, typically a tree array with each node being an array that deals with capable of storing 26 characters or 255 characters (When have no special symbols). This process this takes extra space to reserve upcoming character which is part of node. This mechanism takes lot of extra memory when tree contains dissimilar words.

Optimized Trie Tree

We optimize the trie tree memory mechanism, using of some special collection which is based on key and value pairs. Key indicate inserting character and value indicate tree node. Let us see an example to understand the difference between optimize tree and normalize tree.

Input Words : ["ABC","AZY","IT"]

Normal Trie Tree
                    
       root [A,.......,'I',................]
             |           \    
        [..,'B',..,'Z'][..,'T',..]  
             |       \
     ['','','C',..][..,'Y',..]  



Optimize Trie Tree

    root [A,'I']
         |    \         
    ['B','Z'] ['T']  
         |      | 
       ['C']  ['Y']

Important, some programming languages are internally uses array to represent collection but it is an abstract. Here given code implementation process.

import java.util.HashMap;
/*
   Java Program 
   Implementation trie tree with memory optimization
*/
class TreeNode
{
    // Indicates end of string
    public boolean last;

    public HashMap<Character,TreeNode> children;

    public TreeNode()
    {
        this.children = new HashMap<Character,TreeNode>();

        this.last = false;
    }
}
public class TrieTree
{
    public TreeNode root;

    public TrieTree()
    {
        this.root = new TreeNode();
    }
    public void insert(String text)
    {
        // First get the length of text
        int length = text.length();
   
        // Get the root node
        TreeNode node = this.root;

        for (int level = 0; level < length; ++level)
        {
            
            if (node.children.containsKey(text.charAt(level)) == false)
            {
                // When need to add new Node
                node.children.put(text.charAt(level),new TreeNode());
            }
            // Visit to child node
            node = node.children.get(text.charAt(level));
        }
        if (node != null)
        {
            // Indicates end of string
            node.last = true;
        }
    }
    public boolean search( String text)
    {
        // First get the length of text
        int length = text.length();
      
        // Get the root node
        TreeNode node = this.root;

        for (int level = 0; level < length; ++level)
        {
            
            if (node.children.containsKey(text.charAt(level)) == false)
            {
                return false;
            }
            // Visit to child node
            node = node.children.get(text.charAt(level));
        }
        if (node != null)
        {
            return node.last;
        }
        return false;
    }
    public void display(TreeNode node, String about)
    {
        if (node != null)
        {
            if (node.last == true)
            {
                // When words are complete
                System.out.println(about);
            }

            for (char data : node.children.keySet()) 
            {
                // Visit to child node
                display(node.children.get(data), about + data);
            }
        }
    }

    public static void main(String[] args)
    {
        TrieTree tree = new TrieTree();
        
        // Tree Words
        tree.insert("c");
        tree.insert("cshap");
        tree.insert("php");
        tree.insert("rust");
        tree.insert("python");
        tree.insert("perl");
        tree.insert("code");
        tree.insert("count");
        tree.insert("run");

        System.out.println("\nTree Words ");
        // Display tree node
        tree.display(tree.root,"");


        System.out.println("\nSearch Operation ");

        String text = "code";

        if(tree.search(text))
        {
            System.out.println("word \""+text + "\" are exist");
        }
        else
        {
            System.out.println("word \""+text + "\" are not exist");
        }
        text = "codes";
        if(tree.search(text))
        {
            System.out.println("word \""+text + "\" are exist");
        }
        else
        {
            System.out.println("word \""+text + "\" are not exist");
        }

    }
}

Output

Tree Words
perl
php
python
rust
run
c
cshap
code
count

Search Operation
word "code" are exist
word "codes" are not exist
package main
import "fmt"
/*
   Go Program 
   Implementation trie tree with memory optimization
*/
type TreeNode struct {
    // Indicates end of string
    last bool
    children map[byte] *TreeNode
}
func getTreeNode() * TreeNode {
    var me *TreeNode = &TreeNode {}
    me.children =  make(map[byte] *TreeNode)
    me.last = false
    return me
}
type TrieTree struct {
    root * TreeNode
}
func getTrieTree() * TrieTree {
    var me *TrieTree = &TrieTree {}
    me.root = getTreeNode()
    return me
}
func(this *TrieTree) insert(text string) {
    // First get the length of text
    var length int = len(text)
    // Get the root node
    var node * TreeNode = this.root
    for level := 0 ; level < length ; level++ {
        if _, found := node.children[text[level]] ; found == false {
            // When need to add new Node
            node.children[text[level]] = getTreeNode()
        }
        // Visit to child node
        node = node.children[text[level]]
    }
    if node != nil {
        // Indicates end of string
        node.last = true
    }
}
func(this TrieTree) search(text string) bool {
    // First get the length of text
    var length int = len(text)
    // Get the root node
    var node * TreeNode = this.root
    for level := 0 ; level < length ; level++ {
        if _, found := node.children[text[level]] ; found == false {
            return false
        }
        // Visit to child node
        node = node.children[text[level]]
    }
    if node != nil {
        return node.last
    }
    return false
}
func(this TrieTree) display(node * TreeNode, about string) {
    if node != nil {
        if node.last == true {
            // When words are complete
            fmt.Println(about)
        }
        for k, v := range node.children {
            // Visit to child node
            this.display(v, 
                about + string(k))
        }
    }
}
func main() {
    var tree * TrieTree = getTrieTree()
    // Tree Words
    tree.insert("c")
    tree.insert("cshap")
    tree.insert("php")
    tree.insert("rust")
    tree.insert("python")
    tree.insert("perl")
    tree.insert("code")
    tree.insert("count")
    tree.insert("run")
    fmt.Println("\nTree Words ")
    // Display tree node
    tree.display(tree.root, "")
    fmt.Println("\nSearch Operation ")
    var text string = "code"
    if tree.search(text) {
        fmt.Println("word \""+ text+ "\" are exist")
    } else {
        fmt.Println("word \""+ text+"\" are not exist")
    }
    text = "codes"
    if tree.search(text) {
        fmt.Println("word \""+ text+ "\" are exist")
    } else {
        fmt.Println("word \""+ text+"\" are not exist")
    }
}

Output

Tree Words 
c
cshap
code
count
perl
php
python
rust
run

Search Operation 
word "code" are exist
word "codes" are not exist
// Include header file
#include <iostream>

#include <string>

#include <unordered_map>

using namespace std;
/*
   C++ Program 
   Implementation trie tree with memory optimization
*/
class TreeNode
{
    public:
    // Indicates end of string
    bool last;
    unordered_map < char, TreeNode *> children; 
    TreeNode()
    {
        this->last = false;
    }
};
class TrieTree
{
    public: TreeNode *root;
    TrieTree()
    {
        this->root = new TreeNode();
    }
    void insert(string text)
    {
        // First get the length of text
        int length = text.length();
        // Get the root node
        TreeNode *node = this->root;
        for (int level = 0; level < length; ++level)
        {
            if (node->children.find(text[level]) == node->children.end() )
            {
                // When need to add new Node
                node->children[text[level]] = new TreeNode();
            }
            // Visit to child node
            node = node->children[text[level]];
        }
        if (node != NULL)
        {
            // Indicates end of string
            node->last = true;
        }
    }
    bool search(string text)
    {
        // First get the length of text
        int length = text.length();
        // Get the root node
        TreeNode *node = this->root;
        for (int level = 0; level < length; ++level)
        {
            if (node->children.find(text[level]) == node->children.end())
            {
                return false;
            }
            // Visit to child node
            node = node->children[text[level]];
        }
        if (node != NULL)
        {
            return node->last;
        }
        return false;
    }
    void display(TreeNode *node, string about)
    {
        if (node != NULL)
        {
            if (node->last == true)
            {
                // When words are complete
                cout << about << endl;
            }
            for (auto &data: node->children)
            {
                // Visit to child node
                this->display(node->children[data.first], 
                              about  +  data.first);
            }
        }
    }
};
int main()
{
    TrieTree *tree = new TrieTree();
    // Tree Words
    tree->insert("c");
    tree->insert("cshap");
    tree->insert("php");
    tree->insert("rust");
    tree->insert("python");
    tree->insert("perl");
    tree->insert("code");
    tree->insert("count");
    tree->insert("run");
    cout << "\nTree Words " << endl;
    // Display tree node
    tree->display(tree->root, "");
    cout << "\nSearch Operation " << endl;
    string text = "code";
    if (tree->search(text))
    {
        cout << "word \"" << text << "\" are exist" << endl;
    }
    else
    {
        cout << "word \"" << text << "\" are not exist" << endl;
    }
    text = "codes";
    if (tree->search(text))
    {
        cout << "word \"" << text << "\" are exist" << endl;
    }
    else
    {
        cout << "word \"" << text << "\" are not exist" << endl;
    }
    return 0;
}

Output

Tree Words
perl
python
php
run
rust
c
count
code
cshap

Search Operation
word "code" are exist
word "codes" are not exist
// Include namespace system
using System;
using System.Collections.Generic;
/*
   Csharp Program 
   Implementation trie tree with memory optimization
*/
public class TreeNode
{
    // Indicates end of string
    public Boolean last;
    public Dictionary < char, TreeNode > children;
    public TreeNode()
    {
        this.children = new Dictionary < char, TreeNode > ();
        this.last = false;
    }
}
public class TrieTree
{
    public TreeNode root;
    public TrieTree()
    {
        this.root = new TreeNode();
    }
    public void insert(String text)
    {
        // First get the length of text
        int length = text.Length;
        // Get the root node
        TreeNode node = this.root;
        for (int level = 0; level < length; ++level)
        {
            if (node.children.ContainsKey(text[level]) == false)
            {
                // When need to add new Node
                node.children.Add(text[level], new TreeNode());
            }
            // Visit to child node
            node = node.children[text[level]];
        }
        if (node != null)
        {
            // Indicates end of string
            node.last = true;
        }
    }
    public Boolean search(String text)
    {
        // First get the length of text
        int length = text.Length;
        // Get the root node
        TreeNode node = this.root;
        for (int level = 0; level < length; ++level)
        {
            if (node.children.ContainsKey(text[level]) == false)
            {
                return false;
            }
            // Visit to child node
            node = node.children[text[level]];
        }
        if (node != null)
        {
            return node.last;
        }
        return false;
    }
    public void display(TreeNode node, String about)
    {
        if (node != null)
        {
            if (node.last == true)
            {
                // When words are complete
                Console.WriteLine(about);
            }
            foreach(KeyValuePair < char, TreeNode > data in node.children)
            {
                // Visit to child node
                this.display(data.Value, about + data.Key);
            }
        }
    }
    public static void Main(String[] args)
    {
        TrieTree tree = new TrieTree();
        // Tree Words
        tree.insert("c");
        tree.insert("cshap");
        tree.insert("php");
        tree.insert("rust");
        tree.insert("python");
        tree.insert("perl");
        tree.insert("code");
        tree.insert("count");
        tree.insert("run");
        Console.WriteLine("\nTree Words ");
        // Display tree node
        tree.display(tree.root, "");
        Console.WriteLine("\nSearch Operation ");
        String text = "code";
        if (tree.search(text))
        {
            Console.WriteLine("word \"" + text + "\" are exist");
        }
        else
        {
            Console.WriteLine("word \"" + text + "\" are not exist");
        }
        text = "codes";
        if (tree.search(text))
        {
            Console.WriteLine("word \"" + text + "\" are exist");
        }
        else
        {
            Console.WriteLine("word \"" + text + "\" are not exist");
        }
    }
}

Output

Tree Words
c
cshap
code
count
php
python
perl
rust
run

Search Operation
word "code" are exist
word "codes" are not exist
<?php
/*
   Php Program 
   Implementation trie tree with memory optimization
*/
class TreeNode
{
    // Indicates end of string
    public $last;
    public $children;
    public  function __construct()
    {
        $this->children = array();
        $this->last = false;
    }
}
class TrieTree
{
    public $root;
    public  function __construct()
    {
        $this->root = new TreeNode();
    }
    public  function insert($text)
    {
        // First get the length of text
        $length = strlen($text);
        // Get the root node
        $node = $this->root;
        for ($level = 0; $level < $length; ++$level)
        {
            if (array_key_exists($text[$level], $node->children) == false)
            {
                // When need to add new Node
                $node->children[$text[$level]] = new TreeNode();
            }
            // Visit to child node
            $node = $node->children[$text[$level]];
        }
        if ($node != NULL)
        {
            // Indicates end of string
            $node->last = true;
        }
    }
    public  function search($text)
    {
        // First get the length of text
        $length = strlen($text);
        // Get the root node
        $node = $this->root;
        for ($level = 0; $level < $length; ++$level)
        {
            if (array_key_exists($text[$level], $node->children) == false)
            {
                return false;
            }
            // Visit to child node
            $node = $node->children[$text[$level]];
        }
        if ($node != NULL)
        {
            return $node->last;
        }
        return false;
    }
    public  function display($node, $about)
    {
        if ($node != NULL)
        {
            if ($node->last == true)
            {
                // When words are complete
                echo($about.
                    "\n");
            }
            foreach($node->children as $key => $value)
            {
                // Visit to child node
                $this->display($value, $about.strval($key));
            }
        }
    }
}

function main()
{
    $tree = new TrieTree();
    // Tree Words
    $tree->insert("c");
    $tree->insert("cshap");
    $tree->insert("php");
    $tree->insert("rust");
    $tree->insert("python");
    $tree->insert("perl");
    $tree->insert("code");
    $tree->insert("count");
    $tree->insert("run");
    echo("\nTree Words ".
        "\n");
    // Display tree node
    $tree->display($tree->root, "");
    echo("\nSearch Operation ".
        "\n");
    $text = "code";
    if ($tree->search($text))
    {
        echo("word \"".$text.
            "\" are exist".
            "\n");
    }
    else
    {
        echo("word \"".$text.
            "\" are not exist".
            "\n");
    }
    $text = "codes";
    if ($tree->search($text))
    {
        echo("word \"".$text.
            "\" are exist".
            "\n");
    }
    else
    {
        echo("word \"".$text.
            "\" are not exist".
            "\n");
    }
}
main();

Output

Tree Words
c
cshap
code
count
php
python
perl
rust
run

Search Operation
word "code" are exist
word "codes" are not exist
/*
   Node JS Program 
   Implementation trie tree with memory optimization
*/
class TreeNode
{
    constructor()
    {
        this.children = new Map();
        this.last = false;
    }
}
class TrieTree
{
    constructor()
    {
        this.root = new TreeNode();
    }
    insert(text)
    {
        // First get the length of text
        var length = text.length;
        // Get the root node
        var node = this.root;
        for (var level = 0; level < length; ++level)
        {
            if (node.children.has(text.charAt(level)) == false)
            {
                // When need to add new Node
                node.children.set(text.charAt(level), new TreeNode());
            }
            // Visit to child node
            node = node.children.get(text.charAt(level));
        }
        if (node != null)
        {
            // Indicates end of string
            node.last = true;
        }
    }
    search(text)
    {
        // First get the length of text
        var length = text.length;
        // Get the root node
        var node = this.root;
        for (var level = 0; level < length; ++level)
        {
            if (node.children.has(text.charAt(level)) == false)
            {
                return false;
            }
            // Visit to child node
            node = node.children.get(text.charAt(level));
        }
        if (node != null)
        {
            return node.last;
        }
        return false;
    }
    display(node, about)
    {
        if (node != null)
        {
            if (node.last == true)
            {
                // When words are complete
                console.log(about);
            }
            for (let [key, value] of node.children)
            {
                // Visit to child node
                this.display(value, about + key);
            }
        }
    }
}

function main()
{
    var tree = new TrieTree();
    // Tree Words
    tree.insert("c");
    tree.insert("cshap");
    tree.insert("php");
    tree.insert("rust");
    tree.insert("python");
    tree.insert("perl");
    tree.insert("code");
    tree.insert("count");
    tree.insert("run");
    console.log("\nTree Words ");
    // Display tree node
    tree.display(tree.root, "");
    console.log("\nSearch Operation ");
    var text = "code";
    if (tree.search(text))
    {
        console.log("word \"" + text + "\" are exist");
    }
    else
    {
        console.log("word \"" + text + "\" are not exist");
    }
    text = "codes";
    if (tree.search(text))
    {
        console.log("word \"" + text + "\" are exist");
    }
    else
    {
        console.log("word \"" + text + "\" are not exist");
    }
}
main();

Output

Tree Words
c
cshap
code
count
php
python
perl
rust
run

Search Operation
word "code" are exist
word "codes" are not exist
#   Python 3 Program 
#   Implementation trie tree with memory optimization
class TreeNode :
    #  Indicates end of string
    def __init__(self) :
        self.children = dict()
        self.last = False
    

class TrieTree :
    def __init__(self) :
        self.root = TreeNode()
    
    def insert(self, text) :
        #  First get the length of text
        length = len(text)
        #  Get the root node
        node = self.root
        level = 0
        while (level < length) :
            if ((text[level] in node.children.keys()) == False) :
                #  When need to add new Node
                node.children[text[level]] = TreeNode()
            
            #  Visit to child node
            node = node.children.get(text[level])
            level += 1
        
        if (node != None) :
            #  Indicates end of string
            node.last = True
        
    
    def search(self, text) :
        #  First get the length of text
        length = len(text)
        #  Get the root node
        node = self.root
        level = 0
        while (level < length) :
            if (text[level] not in node.children.keys()) :
                return False
            
            #  Visit to child node
            node = node.children.get(text[level])
            level += 1
        
        if (node != None) :
            return node.last
        
        return False
    
    def display(self, node, about) :
        if (node != None) :
            if (node.last == True) :
                #  When words are complete
                print(about)
            
            for key, value in node.children.items() :
                #  Visit to child node
                self.display(value, about + str(key))
            
        
    

def main() :
    tree = TrieTree()
    #  Tree Words
    tree.insert("c")
    tree.insert("cshap")
    tree.insert("php")
    tree.insert("rust")
    tree.insert("python")
    tree.insert("perl")
    tree.insert("code")
    tree.insert("count")
    tree.insert("run")
    print("\nTree Words ")
    #  Display tree node
    tree.display(tree.root, "")
    print("\nSearch Operation ")
    text = "code"
    if (tree.search(text)) :
        print("word \"", text ,"\" are exist")
    else :
        print("word \"", text ,"\" are not exist")
    
    text = "codes"
    if (tree.search(text)) :
        print("word \"", text ,"\" are exist")
    else :
        print("word \"", text ,"\" are not exist")
    

if __name__ == "__main__": main()

Output

Tree Words
python
php
perl
run
rust
c
count
code
cshap

Search Operation
word " code " are exist
word " codes " are not exist
#   Ruby Program 
#   Implementation trie tree with memory optimization
class TreeNode 
    # Define the accessor and reader of class TreeNode
    attr_reader :last, :children
    attr_accessor :last, :children
    #  Indicates end of string
    def initialize() 
        self.children = Hash.new()
        self.last = false
    end

end

class TrieTree 
    # Define the accessor and reader of class TrieTree
    attr_reader :root
    attr_accessor :root
    def initialize() 
        self.root = TreeNode.new()
    end

    def insert(text) 
        #  First get the length of text
        length = text.length
        #  Get the root node
        node = self.root
        level = 0
        while (level < length) 
            if (node.children.key?(text[level]) == false) 
                #  When need to add new Node
                node.children[text[level]] = TreeNode.new()
            end

            #  Visit to child node
            node = node.children[text[level]]
            level += 1
        end

        if (node != nil) 
            #  Indicates end of string
            node.last = true
        end

    end

    def search(text) 
        #  First get the length of text
        length = text.length
        #  Get the root node
        node = self.root
        level = 0
        while (level < length) 
            if (node.children.key?(text[level]) == false) 
                return false
            end

            #  Visit to child node
            node = node.children[text[level]]
            level += 1
        end

        if (node != nil) 
            return node.last
        end

        return false
    end

    def display(node, about) 
        if (node != nil) 
            if (node.last == true) 
                #  When words are complete
                print(about, "\n")
            end

            node.children.each { | key, value |
                #  Visit to child node
                self.display(value, about + key.to_s)
            }
        end

    end

end

def main() 
    tree = TrieTree.new()
    #  Tree Words
    tree.insert("c")
    tree.insert("cshap")
    tree.insert("php")
    tree.insert("rust")
    tree.insert("python")
    tree.insert("perl")
    tree.insert("code")
    tree.insert("count")
    tree.insert("run")
    print("\nTree Words ", "\n")
    #  Display tree node
    tree.display(tree.root, "")
    print("\nSearch Operation ", "\n")
    text = "code"
    if (tree.search(text)) 
        print("word \"", text ,"\" are exist", "\n")
    else
 
        print("word \"", text ,"\" are not exist", "\n")
    end

    text = "codes"
    if (tree.search(text)) 
        print("word \"", text ,"\" are exist", "\n")
    else
 
        print("word \"", text ,"\" are not exist", "\n")
    end

end

main()

Output

Tree Words 
c
cshap
code
count
php
python
perl
rust
run

Search Operation 
word "code" are exist
word "codes" are not exist

import scala.collection.mutable._;
/*
   Scala Program 
   Implementation trie tree with memory optimization
*/
class TreeNode(
    // Indicates end of string
    var last: Boolean,
        var children: HashMap[Character, TreeNode])
{
    def this()
    {
        this(false, new HashMap[Character, TreeNode]());
    }
}
class TrieTree(var root: TreeNode)
{
    def this()
    {
        this(new TreeNode());
    }
    def insert(text: String): Unit = {
        // First get the length of text
        var length: Int = text.length();
        // Get the root node
        var node: TreeNode = this.root;
        var level: Int = 0;
        while (level < length)
        {
            if (node.children.contains(text.charAt(level)) == false)
            {
                // When need to add new Node
                node.children.addOne(text.charAt(level), new TreeNode());
            }
            // Visit to child node
            node = node.children.get(text.charAt(level)).get;
            level += 1;
        }
        if (node != null)
        {
            // Indicates end of string
            node.last = true;
        }
    }
    def search(text: String): Boolean = {
        // First get the length of text
        var length: Int = text.length();
        // Get the root node
        var node: TreeNode = this.root;
        var level: Int = 0;
        while (level < length)
        {
            if (node.children.contains(text.charAt(level)) == false)
            {
                return false;
            }
            // Visit to child node
            node = node.children.get(text.charAt(level)).get;
            level += 1;
        }
        if (node != null)
        {
            return node.last;
        }
        return false;
    }
    def display(node: TreeNode, about: String): Unit = {
        if (node != null)
        {
            if (node.last == true)
            {
                // When words are complete
                println(about);
            }
            for ((key, value) <- node.children)
            {
                // Visit to child node
                display(value, about + key.toString());
            }
        }
    }
}
object Main
{
    def main(args: Array[String]): Unit = {
        var tree: TrieTree = new TrieTree();
        // Tree Words
        tree.insert("c");
        tree.insert("cshap");
        tree.insert("php");
        tree.insert("rust");
        tree.insert("python");
        tree.insert("perl");
        tree.insert("code");
        tree.insert("count");
        tree.insert("run");
        println("\nTree Words ");
        // Display tree node
        tree.display(tree.root, "");
        println("\nSearch Operation ");
        var text: String = "code";
        if (tree.search(text))
        {
            println("word \"" + text + "\" are exist");
        }
        else
        {
            println("word \"" + text + "\" are not exist");
        }
        text = "codes";
        if (tree.search(text))
        {
            println("word \"" + text + "\" are exist");
        }
        else
        {
            println("word \"" + text + "\" are not exist");
        }
    }
}

Output

Tree Words
perl
php
python
rust
run
c
cshap
code
count

Search Operation
word "code" are exist
word "codes" are not exist
import Foundation;
/*
   Swift 4 Program 
   Implementation trie tree with memory optimization
*/
class TreeNode
{
    // Indicates end of string
    var last: Bool;
    var children: [Character : TreeNode?];
    init()
        {
            self.children = [Character : TreeNode? ]();
            self.last = false;
        }
    }
    class TrieTree
    {
        var root: TreeNode? ;
        init()
        {
            self.root = TreeNode();
        }
        func insert(_ data: String)
        {
            let text = Array(data);
            // First get the length of text
            let length: Int = text.count;
            // Get the root node
            var node: TreeNode? = self.root;
            var level: Int = 0;
            while (level < length)
            {
                if (node!.children.keys.contains(text[level]) == false)
                {
                    // When need to add new Node
                    node!.children[text[level]] = TreeNode();
                }
                // Visit to child node
                node = node!.children[text[level]]!;
                level += 1;
            }
            if (node  != nil)
            {
                // Indicates end of string
                node!.last = true;
            }
        }
        func search(_ data: String) -> Bool
        {
            let text = Array(data);
            // First get the length of text
            let length: Int = text.count;
            // Get the root node
            var node: TreeNode? = self.root;
            var level: Int = 0;
            while (level < length)
            {
                if (node!.children.keys.contains(text[level]) == false)
                {
                    return false;
                }
                // Visit to child node
                node = node!.children[text[level]]!;
                level += 1;
            }
            if (node  != nil)
            {
                return node!.last;
            }
            return false;
        }
        func display(_ node: TreeNode? , _ about : String)
        {
            if (node  != nil)
            {
                if (node!.last == true)
                {
                    // When words are complete
                    print(about);
                }
                for (key, value) in node!.children
                {
                    // Visit to child node
                    self.display(value, about + String(key));
                }
            }
        }
    }
    func main()
    {
        let tree: TrieTree = TrieTree();
        // Tree Words
        tree.insert("c");
        tree.insert("cshap");
        tree.insert("php");
        tree.insert("rust");
        tree.insert("python");
        tree.insert("perl");
        tree.insert("code");
        tree.insert("count");
        tree.insert("run");
        print("\nTree Words ");
        // Display tree node
        tree.display(tree.root, "");
        print("\nSearch Operation ");
        var text: String = "code";
        if (tree.search(text))
        {
            print("word \"", text ,"\" are exist");
        }
        else
        {
            print("word \"", text ,"\" are not exist");
        }
        text = "codes";
        if (tree.search(text))
        {
            print("word \"", text ,"\" are exist");
        }
        else
        {
            print("word \"", text ,"\" are not exist");
        }
    }
    main();

Output

Tree Words
rust
run
python
perl
php
c
cshap
count
code

Search Operation
word " code " are exist
word " codes " are not exist
/*
   Kotlin Program 
   Implementation trie tree with memory optimization
*/
class TreeNode
{
    // Indicates end of string
    var last: Boolean;
    var children: HashMap < Char, TreeNode > ;
    constructor()
    {
        this.children = HashMap < Char, TreeNode > ();
        this.last = false;
    }
}
class TrieTree
{
    var root: TreeNode ? ;
    constructor()
    {
        this.root = TreeNode();
    }
    fun insert(text: String): Unit
    {
        // First get the length of text
        val length: Int = text.length;
        // Get the root node
        var node: TreeNode ? = this.root;
        var level: Int = 0;
        while (level < length)
        {
            if (node?.children?.containsKey(text.get(level)) == false)
            {
                // When need to add new Node
                node.children.put(text.get(level), TreeNode());
            }
            // Visit to child node
            node = node?.children!!.getValue(text.get(level));
            level += 1;
        }
        if (node != null)
        {
            // Indicates end of string
            node.last = true;
        }
    }
    fun search(text: String): Boolean
    {
        // First get the length of text
        val length: Int = text.length;
        // Get the root node
        var node: TreeNode ? = this.root;
        var level: Int = 0;
        while (level < length)
        {
            if (node?.children!!.containsKey(text.get(level)) == false)
            {
                return false;
            }
            // Visit to child node
            node = node.children.getValue(text.get(level));
            level += 1;
        }
        if (node != null)
        {
            return node.last;
        }
        return false;
    }
    fun display(node: TreeNode ? , about : String): Unit
    {
        if (node != null)
        {
            if (node.last == true)
            {
                // When words are complete
                println(about);
            }
            for ((key, value) in node.children)
            {
                // Visit to child node
                this.display(value, about + key.toString());
            }
        }
    }
}
fun main(args: Array < String > ): Unit
{
    val tree: TrieTree = TrieTree();
    // Tree Words
    tree.insert("c");
    tree.insert("cshap");
    tree.insert("php");
    tree.insert("rust");
    tree.insert("python");
    tree.insert("perl");
    tree.insert("code");
    tree.insert("count");
    tree.insert("run");
    println("\nTree Words ");
    // Display tree node
    tree.display(tree.root, "");
    println("\nSearch Operation ");
    var text: String = "code";
    if (tree.search(text))
    {
        println("word \"" + text + "\" are exist");
    }
    else
    {
        println("word \"" + text + "\" are not exist");
    }
    text = "codes";
    if (tree.search(text))
    {
        println("word \"" + text + "\" are exist");
    }
    else
    {
        println("word \"" + text + "\" are not exist");
    }
}

Output

Tree Words
perl
php
python
rust
run
c
cshap
code
count

Search Operation
word "code" are exist
word "codes" are not exist
Last updated on by Kalkicode




Comment

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