In data structure, radix tree is a optimized version of a trie. Generally of Trie tree is capable to hold a single character. But radix tree is capable to store hole word.

## Implementation

Given collection of words, Our goal is to using of this word construct a valid radix tree. Suppose following data are inserting in radix tree ["romane", "romanus", "romulus", "rubens", "ruber", "rubicon", "rubicundus"]. This example taken from wikipedia.

``````import java.util.Vector;
// Java Program for
class TreeNode
{
public String label;
public Vector < TreeNode > child;
public TreeNode()
{
this.label = "";
this.child = new Vector < TreeNode > ();
}
public TreeNode(String value)
{
this.label = value;
this.child = new Vector < TreeNode > ();
}
}
{
public TreeNode root;
{
this.root = new TreeNode("");
}
private int matchingCharacters(String word, TreeNode node)
{
int matches   = 0;
int minLength = 0;

if (node.label.length() >= word.length())
{
minLength = word.length();
}
else if (node.label.length() < word.length())
{
minLength = node.label.length();
}
if (minLength > 0)
{
// Count matches characters
for (int i = 0; i < minLength; i++)
{
if (word.charAt(i) == node.label.charAt(i))
{
// When characters are same
matches++;
}
else
{
// When characters are not same
return matches;
}
}
}
// Return the current number of matches
return matches;
}
// Add node in proper place
private void insertProcess(String word, TreeNode node)
{
int matches = matchingCharacters(word, node);
if ((matches == 0) || (node == root) ||
((matches > 0) && (matches < word.length()) &&
(matches >= node.label.length())))
{
boolean inserted = false;
String newWordPart = word.substring(matches, word.length());
for (int i = 0; i < node.child.size(); ++i)
{
if (node.child.get(i).label.startsWith(
"" + newWordPart.charAt(0)))
{
inserted = true;
insertProcess(newWordPart, node.child.get(i));
}
}
if (inserted == false)
{
}
}
else if (matches < word.length())
{
String commonRoot = word.substring(0, matches);
String branchPreviouslabel = node.label.substring(
matches, node.label.length());
String branchNewlabel = word.substring(matches, word.length());
node.label = commonRoot;
TreeNode newNodePreviouslabel = new TreeNode(branchPreviouslabel);

// Add current node child to new node
for (int i = 0; i < node.child.size(); ++i)
{
}

// Clear node element
node.child.clear();

}
else if (matches > node.label.length())
{
String newLabel = node.label.substring(
node.label.length(), word.length());

}
}
public void insert(String word)
{
this.insertProcess(word, this.root);
}
// Display the preorder of tree elements
public void printPreorder(TreeNode node)
{
if (node == null)
{
return;
}
// Display node value
System.out.println(node.label);

for (int i = 0; i < node.child.size(); ++i)
{
// Visit child node
printPreorder(node.child.get(i));
}
}
public static void main(String[] args)
{
tree.insert("romane");
tree.insert("romanus");
tree.insert("romulus");
tree.insert("rubens");
tree.insert("ruber");
tree.insert("rubicon");
tree.insert("rubicundus");
/*
r
/  \
/    \
/      \
/        \
om        ub
/  \      /  \
an  ulus  e    ic
/ \       / \   / \
e   us    ns  r on  undus

*/
System.out.print("Preorder Tree Data ");
// Print Tree nodes
tree.printPreorder(tree.root);
}
}``````

#### Output

``````Preorder Tree Data
r
om
an
e
us
ulus
ub
e
ns
r
ic
on
undus``````
``````package main
import "fmt"
import "strings"
// Go Program for
type TreeNode struct {
label string
child [] *TreeNode
}
func getTreeNode(value string) * TreeNode {
var me *TreeNode = &TreeNode {}
me.label = value
me.child = make([] *TreeNode,0)
return me
}

root * TreeNode
}
me.root = getTreeNode("")
return me
}
node * TreeNode) int {
var matches int = 0
var minLength int = 0
if len(node.label) >= len(word) {
minLength = len(word)
} else if len(node.label) < len(word) {
minLength = len(node.label)
}
if minLength > 0 {
// Count matches characters
for i := 0 ; i < minLength ; i++ {
if word[i] == node.label[i] {
// When characters are same
matches++
} else {
// When characters are not same
return matches
}
}
}
// Return the current number of matches
return matches
}
// Add node in proper place
func(this RadixTree) insertProcess(word string, node * TreeNode) {
var matches int = this.matchingCharacters(word, node)
if (matches == 0) || (node == this.root) || (
(matches > 0) && (matches < len(word)) && (
matches >= len(node.label))) {
var inserted bool = false
var newWordPart string = word[matches : len(word) ]
for i := 0 ; i < len(node.child) ; i++ {
if strings.HasPrefix(node.child[i].label,
string(newWordPart[0])) {
inserted = true
this.insertProcess(newWordPart, node.child[i])
}
}
if inserted == false {
node.child = append(node.child, getTreeNode(newWordPart))
}
} else if matches < len(word) {
var commonRoot string = word[0 : matches]
var branchPreviouslabel string = node.label[matches : len(node.label)]
var branchNewlabel string = word[matches : len(word)]
node.label = commonRoot
var newNodePreviouslabel * TreeNode = getTreeNode(branchPreviouslabel)
// Add current node child to new node
for i := 0 ; i < len(node.child) ; i++ {
newNodePreviouslabel.child = append(newNodePreviouslabel.child,
node.child[i])
}
// Clear node element
node.child = nil
node.child = append(node.child, newNodePreviouslabel)
node.child = append(node.child, getTreeNode(branchNewlabel))
} else if matches > len(node.label) {
var newLabel string = node.label[len(node.label) : len(word)]
node.child = append(node.child, getTreeNode(newLabel))
}
}
this.insertProcess(word, this.root)
}
// Display the preorder of tree elements
func(this RadixTree) printPreorder(node * TreeNode) {
if node == nil {
return
}
// Display node value
fmt.Println(node.label)
for i := 0 ; i < len(node.child) ; i++ {
// Visit child node
this.printPreorder(node.child[i])
}
}
func main() {
tree.insert("romane")
tree.insert("romanus")
tree.insert("romulus")
tree.insert("rubens")
tree.insert("ruber")
tree.insert("rubicon")
tree.insert("rubicundus")
/*
r
/  \
/    \
/      \
/        \
om        ub
/  \      /  \
an  ulus  e    ic
/ \       / \   / \
e   us    ns  r on  undus
*/
fmt.Print("Preorder Tree Data ")
// Tree Tree nodes
tree.printPreorder(tree.root)
}``````

#### Output

``````Preorder Tree Data
r
om
an
e
us
ulus
ub
e
ns
r
ic
on
undus``````
``````// Include header file
#include <iostream>
#include <string>
#include <vector>

using namespace std;
// C++ Program for
class TreeNode
{
public: string label;
vector < TreeNode *> child;
TreeNode(){
this->label = "";
}
TreeNode(string value)
{
this->label = value;
}
};
{
public: TreeNode *root;
{
this->root = new TreeNode("");
}
int matchingCharacters(string word, TreeNode *node)
{
int matches = 0;
int minLength = 0;
if (node->label.length() >= word.length())
{
minLength = word.length();
}
else if (node->label.length() < word.length())
{
minLength = node->label.length();
}
if (minLength > 0)
{
// Count matches characters
for (int i = 0; i < minLength; i++)
{
if (word[i] == node->label[i])
{
// When characters are same
matches++;
}
else
{
// When characters are not same
return matches;
}
}
}
// Return the current number of matches
return matches;
}
// Add node in proper place
void insertProcess(string word, TreeNode *node)
{
int matches = this->matchingCharacters(word, node);
if ((matches == 0) || (node == this->root) ||
((matches > 0) && (matches < word.length()) &&
(matches >= node->label.length())))
{
bool inserted = false;
string newWordPart = word.substr(matches, word.length()-matches);
for (int i = 0; i < node->child.size(); ++i)
{
if (node->child.at(i)->label[0] == newWordPart[0])
{
inserted = true;
this->insertProcess(newWordPart, node->child.at(i));
}
}
if (inserted == false)
{
node->child.push_back(new TreeNode(newWordPart));
}
}
else if (matches < word.length())
{
string commonRoot = word.substr(0, matches);
string branchPreviouslabel = node->label.substr(matches, node->label.length()-matches);
string branchNewlabel = word.substr(matches, word.length()-matches);
node->label = commonRoot;
TreeNode *newNodePreviouslabel = new TreeNode(branchPreviouslabel);
// Add current node child to new node
for (int i = 0; i < node->child.size(); ++i)
{
newNodePreviouslabel->child.push_back(node->child.at(i));
}
// Clear node element
node->child.clear();
node->child.push_back(newNodePreviouslabel);
node->child.push_back(new TreeNode(branchNewlabel));
}
else if (matches > node->label.length())
{
string newLabel =
node->label.substr(node->label.length(), word.length());
node->child.push_back(new TreeNode(newLabel));
}
}
void insert(string word)
{
this->insertProcess(word, this->root);
}
// Display the preorder of tree elements
void printPreorder(TreeNode *node)
{
if (node == NULL)
{
return;
}
// Display node value
cout << node->label << endl;
for (int i = 0; i < node->child.size(); ++i)
{
// Visit child node
this->printPreorder(node->child.at(i));
}
}
};
int main()
{
tree->insert("romane");
tree->insert("romanus");
tree->insert("romulus");
tree->insert("rubens");
tree->insert("ruber");
tree->insert("rubicon");
tree->insert("rubicundus");
/*
r
/  \
/    \
/      \
/        \
om        ub
/  \      /  \
an  ulus  e    ic
/ \       / \   / \
e   us    ns  r on  undus

*/
cout << "Preorder Tree Data ";
// Display Tree nodes
tree->printPreorder(tree->root);
return 0;
}``````

#### Output

``````Preorder Tree Data
r
om
an
e
us
ulus
ub
e
ns
r
ic
on
undus``````
``````// Include namespace system
using System;
using System.Collections.Generic;
// Csharp Program for
public class TreeNode
{
public String label;
public List < TreeNode > child;
public TreeNode()
{
this.label = "";
this.child = new List < TreeNode > ();
}
public TreeNode(String value)
{
this.label = value;
this.child = new List < TreeNode > ();
}
}
{
public TreeNode root;
{
this.root = new TreeNode("");
}
private int matchingCharacters(String word, TreeNode node)
{
int matches = 0;
int minLength = 0;
if (node.label.Length >= word.Length)
{
minLength = word.Length;
}
else if (node.label.Length < word.Length)
{
minLength = node.label.Length;
}
if (minLength > 0)
{
// Count matches characters
for (int i = 0; i < minLength; i++)
{
if (word[i] == node.label[i])
{
// When characters are same
matches++;
}
else
{
// When characters are not same
return matches;
}
}
}
// Return the current number of matches
return matches;
}
// Add node in proper place
private void insertProcess(String word, TreeNode node)
{
int matches = this.matchingCharacters(word, node);
if ((matches == 0) || (node == this.root) ||
((matches > 0) && (matches < word.Length) &&
(matches >= node.label.Length)))
{
Boolean inserted = false;
String newWordPart = word.Substring(matches, word.Length - matches);
for (int i = 0; i < node.child.Count; ++i)
{
if (node.child[i].label.StartsWith("" + newWordPart[0]))
{
inserted = true;
this.insertProcess(newWordPart, node.child[i]);
}
}
if (inserted == false)
{
}
}
else if (matches < word.Length)
{
String commonRoot = word.Substring(0, matches);
String branchPreviouslabel = node.label.Substring(matches, node.label.Length- matches);
String branchNewlabel = word.Substring(matches, word.Length - matches);
node.label = commonRoot;
TreeNode newNodePreviouslabel = new TreeNode(branchPreviouslabel);
// Add current node child to new node
for (int i = 0; i < node.child.Count; ++i)
{
}
// Clear node element
node.child.Clear();
}
else if (matches > node.label.Length)
{
String newLabel = node.label.Substring(node.label.Length, word.Length);
}
}
public void insert(String word)
{
this.insertProcess(word, this.root);
}
// Display the preorder of tree elements
public void printPreorder(TreeNode node)
{
if (node == null)
{
return;
}
// Display node value
Console.WriteLine(node.label);
for (int i = 0; i < node.child.Count; ++i)
{
// Visit child node
this.printPreorder(node.child[i]);
}
}
public static void Main(String[] args)
{
tree.insert("romane");
tree.insert("romanus");
tree.insert("romulus");
tree.insert("rubens");
tree.insert("ruber");
tree.insert("rubicon");
tree.insert("rubicundus");
/*
r
/  \
/    \
/      \
/        \
om        ub
/  \      /  \
an  ulus  e    ic
/ \       / \   / \
e   us    ns  r on  undus

*/
Console.Write("Preorder Tree Data ");
// Show Tree nodes
tree.printPreorder(tree.root);
}
}``````

#### Output

``````Preorder Tree Data
r
om
an
e
us
ulus
ub
e
ns
r
ic
on
undus``````
``````<?php
// Php Program for
class TreeNode
{
public \$label;
public \$child;

public  function __construct(\$value)
{
\$this->label = \$value;
\$this->child = array();
}
}
{
public \$root;
public  function __construct()
{
\$this->root = new TreeNode("");
}
private
function matchingCharacters(\$word, \$node)
{
\$matches = 0;
\$minLength = 0;
if (strlen(\$node->label) >= strlen(\$word))
{
\$minLength = strlen(\$word);
}
else if (strlen(\$node->label) < strlen(\$word))
{
\$minLength = strlen(\$node->label);
}
if (\$minLength > 0)
{
// Count matches characters
for (\$i = 0; \$i < \$minLength; \$i++)
{
if (\$word[\$i] == \$node->label[\$i])
{
// When characters are same
\$matches++;
}
else
{
// When characters are not same
return \$matches;
}
}
}
// Return the current number of matches
return \$matches;
}
// Add node in proper place
private
function insertProcess(\$word, \$node)
{
\$matches = \$this->matchingCharacters(\$word, \$node);
if ((\$matches == 0) || (\$node == \$this->root) ||
((\$matches > 0) && (\$matches < strlen(\$word)) &&
(\$matches >= strlen(\$node->label))))
{
\$inserted = false;
\$newWordPart = substr(\$word, \$matches, strlen(\$word) - \$matches);
for (\$i = 0; \$i < count(\$node->child); ++\$i)
{
if (\$node->child[\$i]->label[0] == \$newWordPart[0])
{
\$inserted = true;
\$this->insertProcess(\$newWordPart, \$node->child[\$i]);
}
}
if (\$inserted == false)
{
\$node->child[] = new TreeNode(\$newWordPart);
}
}
else if (\$matches < strlen(\$word))
{
\$commonRoot = substr(\$word, 0, \$matches - 0);
\$branchPreviouslabel = substr(\$node->label,
\$matches, strlen(\$node->label) - \$matches);
\$branchNewlabel = substr(\$word,
\$matches, strlen(\$word) - \$matches);
\$node->label = \$commonRoot;
\$newNodePreviouslabel = new TreeNode(\$branchPreviouslabel);
// Add current node child to new node
for (\$i = 0; \$i < count(\$node->child); ++\$i)
{
\$newNodePreviouslabel->child[] = \$node->child[\$i];
}
// Clear node element
\$node->child = array();
\$node->child[] = \$newNodePreviouslabel;
\$node->child[] = new TreeNode(\$branchNewlabel);
}
else if (\$matches > strlen(\$node->label))
{
\$newLabel = substr(\$node->label,
strlen(\$node->label),
strlen(\$word) - strlen(\$node->label));
\$node->child[] = new TreeNode(\$newLabel);
}
}
public  function insert(\$word)
{
\$this->insertProcess(\$word, \$this->root);
}
// Display the preorder of tree elements
public  function printPreorder(\$node)
{
if (\$node == NULL)
{
return;
}
// Display node value
echo(\$node->label.
"\n");
for (\$i = 0; \$i < count(\$node->child); ++\$i)
{
// Visit child node
\$this->printPreorder(\$node->child[\$i]);
}
}
}

function main()
{
\$tree->insert("romane");
\$tree->insert("romanus");
\$tree->insert("romulus");
\$tree->insert("rubens");
\$tree->insert("ruber");
\$tree->insert("rubicon");
\$tree->insert("rubicundus");
/*
r
/  \
/    \
/      \
/        \
om        ub
/  \      /  \
an  ulus  e    ic
/ \       / \   / \
e   us    ns  r on  undus
*/
echo("Preorder Tree Data ");
// Tree Tree nodes
\$tree->printPreorder(\$tree->root);
}
main();``````

#### Output

``````Preorder Tree Data
r
om
an
e
us
ulus
ub
e
ns
r
ic
on
undus``````
``````// Node JS Program for
class TreeNode
{

constructor(value)
{
this.label = value;
this.child =  [];
}
}
{
constructor()
{
this.root = new TreeNode("");
}
matchingCharacters(word, node)
{
var matches = 0;
var minLength = 0;
if (node.label.length >= word.length)
{
minLength = word.length;
}
else if (node.label.length < word.length)
{
minLength = node.label.length;
}
if (minLength > 0)
{
// Count matches characters
for (var i = 0; i < minLength; i++)
{
if (word.charAt(i) == node.label.charAt(i))
{
// When characters are same
matches++;
}
else
{
// When characters are not same
return matches;
}
}
}
// Return the current number of matches
return matches;
}
// Add node in proper place
insertProcess(word, node)
{
var matches = this.matchingCharacters(word, node);
if ((matches == 0) || (node == this.root) ||
((matches > 0) && (matches < word.length) &&
(matches >= node.label.length)))
{
var inserted = false;
var newWordPart = word.substring(matches, word.length);
for (var i = 0; i < node.child.length; ++i)
{
if (node.child[i].label.startsWith("" + newWordPart.charAt(0)))
{
inserted = true;
this.insertProcess(newWordPart, node.child[i]);
}
}
if (inserted == false)
{
node.child.push(new TreeNode(newWordPart));
}
}
else if (matches < word.length)
{
var commonRoot = word.substring(0, matches);
var branchPreviouslabel =
node.label.substring(matches, node.label.length);
var branchNewlabel = word.substring(matches, word.length);
node.label = commonRoot;
var newNodePreviouslabel = new TreeNode(branchPreviouslabel);
// Add current node child to new node
for (var i = 0; i < node.child.length; ++i)
{
newNodePreviouslabel.child.push(node.child[i]);
}
// Clear node element
node.child = [];
node.child.push(newNodePreviouslabel);
node.child.push(new TreeNode(branchNewlabel));
}
else if (matches > node.label.length)
{
var newLabel = node.label.substring(
node.label.length, word.length);
node.child.push(new TreeNode(newLabel));
}
}
insert(word)
{
this.insertProcess(word, this.root);
}
// Display the preorder of tree elements
printPreorder(node)
{
if (node == null)
{
return;
}
// Display node value
console.log(node.label);
for (var i = 0; i < node.child.length; ++i)
{
// Visit child node
this.printPreorder(node.child[i]);
}
}
}

function main()
{
tree.insert("romane");
tree.insert("romanus");
tree.insert("romulus");
tree.insert("rubens");
tree.insert("ruber");
tree.insert("rubicon");
tree.insert("rubicundus");
/*
r
/  \
/    \
/      \
/        \
om        ub
/  \      /  \
an  ulus  e    ic
/ \       / \   / \
e   us    ns  r on  undus
*/
process.stdout.write("Preorder Tree Data ");
// Tree Tree nodes
tree.printPreorder(tree.root);
}
main();``````

#### Output

``````Preorder Tree Data
r
om
an
e
us
ulus
ub
e
ns
r
ic
on
undus``````
``````#  Python 3 Program for
class TreeNode :
def __init__(self) :
self.label = ""
self.child = []

def __init__(self, value) :
self.label = value
self.child = []

def __init__(self) :
self.root = TreeNode("")

def matchingCharacters(self, word, node) :
matches = 0
minLength = 0
if (len(node.label) >= len(word)) :
minLength = len(word)
elif (len(node.label) < len(word)) :
minLength = len(node.label)

if (minLength > 0) :
i = 0
#  Count matches characters
while (i < minLength) :
if (word[i] == node.label[i]) :
#  When characters are same
matches += 1
else :
#  When characters are not same
return matches

i += 1

#  Return the current number of matches
return matches

#  Add node in proper place
def insertProcess(self, word, node) :
matches = self.matchingCharacters(word, node)
if ((matches == 0) or(node == self.root) or
((matches > 0) and(matches < len(word)) and
(matches >= len(node.label)))) :
inserted = False
newWordPart = word[matches: len(word)]
i = 0
while (i < len(node.child)) :
if (node.child[i].label[0] == newWordPart[0]) :
inserted = True
self.insertProcess(newWordPart, node.child[i])

i += 1

if (inserted == False) :
node.child.append(TreeNode(newWordPart))

elif (matches < len(word)) :
commonRoot = word[0: matches]
branchPreviouslabel = node.label[matches: len(node.label)]
branchNewlabel = word[matches: len(word)]
node.label = commonRoot
newNodePreviouslabel = TreeNode(branchPreviouslabel)
i = 0
#  Add current node child to new node
while (i < len(node.child)) :
newNodePreviouslabel.child.append(node.child[i])
i += 1

#  Clear node element
node.child.clear()
node.child.append(newNodePreviouslabel)
node.child.append(TreeNode(branchNewlabel))
elif (matches > len(node.label)) :
newLabel = node.label[len(node.label): len(word)]
node.child.append(TreeNode(newLabel))

def insert(self, word) :
self.insertProcess(word, self.root)

#  Display the preorder of tree elements
def printPreorder(self, node) :
if (node == None) :
return

#  Display node value
print(node.label)
i = 0
while (i < len(node.child)) :
#  Visit child node
self.printPreorder(node.child[i])
i += 1

def main() :
tree.insert("romane")
tree.insert("romanus")
tree.insert("romulus")
tree.insert("rubens")
tree.insert("ruber")
tree.insert("rubicon")
tree.insert("rubicundus")
#                   r
#                  /  \
#                 /    \
#                /      \
#               /        \
#              om        ub
#             /  \      /  \
#            an  ulus  e    ic
#           / \       / \   / \
#          e   us    ns  r on  undus
print("Preorder Tree Data ", end = "")
#  Tree Tree nodes
tree.printPreorder(tree.root)

if __name__ == "__main__": main()``````

#### Output

``````Preorder Tree Data
r
om
an
e
us
ulus
ub
e
ns
r
ic
on
undus``````
``````#  Ruby Program for
class TreeNode
# Define the accessor and reader of class TreeNode
attr_accessor :label, :child
def initialize()
self.label = ""
self.child = []
end

def initialize(value)
self.label = value
self.child = []
end

end

attr_accessor :root
def initialize()
self.root = TreeNode.new("")
end

def matchingCharacters(word, node)
matches = 0
minLength = 0
if (node.label.length >= word.length)
minLength = word.length
elsif (node.label.length < word.length)
minLength = node.label.length
end

if (minLength > 0)
i = 0
#  Count matches characters
while (i < minLength)
if (word[i] == node.label[i])
#  When characters are same
matches += 1
else

#  When characters are not same
return matches
end

i += 1
end

end

#  Return the current number of matches
return matches
end

#  Add node in proper place
def insertProcess(word, node)
matches = self.matchingCharacters(word, node)
if ((matches == 0) || (node == self.root) ||
((matches > 0) && (matches < word.length) &&
(matches >= node.label.length)))
inserted = false
newWordPart = word[matches...word.length]
i = 0
while (i < node.child.length)
if (node.child[i].label[0] == newWordPart[0].to_s)
inserted = true
self.insertProcess(newWordPart, node.child[i])
end

i += 1
end

if (inserted == false)
node.child.push(TreeNode.new(newWordPart))
end

elsif (matches < word.length)
commonRoot = word[0...matches]
branchPreviouslabel = node.label[matches...node.label.length]
branchNewlabel = word[matches...word.length]
node.label = commonRoot
newNodePreviouslabel = TreeNode.new(branchPreviouslabel)
i = 0
#  Add current node child to new node
while (i < node.child.length)
newNodePreviouslabel.child.push(node.child[i])
i += 1
end

#  Clear node element
node.child.clear()
node.child.push(newNodePreviouslabel)
node.child.push(TreeNode.new(branchNewlabel))
elsif (matches > node.label.length)
newLabel = node.label[node.label.length...word.length]
node.child.push(TreeNode.new(newLabel))
end

end

def insert(word)
self.insertProcess(word, self.root)
end

#  Display the preorder of tree elements
def printPreorder(node)
if (node == nil)
return
end

#  Display node value
print(node.label, "\n")
i = 0
while (i < node.child.length)
#  Visit child node
self.printPreorder(node.child[i])
i += 1
end

end

end

def main()
tree.insert("romane")
tree.insert("romanus")
tree.insert("romulus")
tree.insert("rubens")
tree.insert("ruber")
tree.insert("rubicon")
tree.insert("rubicundus")
#            r
#           /  \
#          /    \
#         /      \
#        /        \
#       om        ub
#      /  \      /  \
#     an  ulus  e    ic
#    / \       / \   / \
#   e   us    ns  r on  undus
print("Preorder Tree Data ")
#  Tree Tree nodes
tree.printPreorder(tree.root)
end

main()``````

#### Output

``````Preorder Tree Data
r
om
an
e
us
ulus
ub
e
ns
r
ic
on
undus
``````
``````import scala.collection.mutable._;
// Scala Program for
class TreeNode(var label: String,
var child: ArrayBuffer[TreeNode])
{
def this()
{
this("", new ArrayBuffer[TreeNode]())
}
def this(value: String)
{
this(value, new ArrayBuffer[TreeNode]())
}
}
{
def this()
{
this(new TreeNode(""));
}
def matchingCharacters(word: String, node: TreeNode): Int = {
var matches: Int = 0;
var minLength: Int = 0;
if (node.label.length() >= word.length())
{
minLength = word.length();
}
else if (node.label.length() < word.length())
{
minLength = node.label.length();
}
if (minLength > 0)
{
var i: Int = 0;
// Count matches characters
while (i < minLength)
{
if (word.charAt(i) == node.label.charAt(i))
{
// When characters are same
matches += 1;
}
else
{
// When characters are not same
return matches;
}
i += 1;
}
}
// Return the current number of matches
return matches;
}
// Add node in proper place
def insertProcess(word: String, node: TreeNode): Unit = {
var matches: Int = matchingCharacters(word, node);
if ((matches == 0) || (node == root) || ((matches > 0) &&
(matches < word.length()) && (matches >= node.label.length())))
{
var inserted: Boolean = false;
var newWordPart: String = word.substring(matches, word.length());
var i: Int = 0;
while (i < node.child.size)
{
if (node.child(i).label.startsWith(
"" + newWordPart.charAt(0).toString()))
{
inserted = true;
insertProcess(newWordPart, node.child(i));
}
i += 1;
}
if (inserted == false)
{
node.child += new TreeNode(newWordPart);
}
}
else if (matches < word.length())
{
var commonRoot: String = word.substring(0, matches);
var branchPreviouslabel: String = node.label.substring(
matches, node.label.length());
var branchNewlabel: String = word.substring(
matches, word.length());
node.label = commonRoot;
var newNodePreviouslabel: TreeNode =
new TreeNode(branchPreviouslabel);
var i: Int = 0;
// Add current node child to new node
while (i < node.child.size)
{
newNodePreviouslabel.child += node.child(i);
i += 1;
}
// Clear node element
node.child.clear();
node.child += newNodePreviouslabel;
node.child += new TreeNode(branchNewlabel);
}
else if (matches > node.label.length())
{
var newLabel: String = node.label.substring(
node.label.length(), word.length());
node.child += new TreeNode(newLabel);
}
}
def insert(word: String): Unit = {
this.insertProcess(word, this.root);
}
// Display the preorder of tree elements
def printPreorder(node: TreeNode): Unit = {
if (node == null)
{
return;
}
// Display node value
println(node.label);
var i: Int = 0;
while (i < node.child.size)
{
// Visit child node
printPreorder(node.child(i));
i += 1;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
tree.insert("romane");
tree.insert("romanus");
tree.insert("romulus");
tree.insert("rubens");
tree.insert("ruber");
tree.insert("rubicon");
tree.insert("rubicundus");
/*
r
/  \
/    \
/      \
/        \
om        ub
/  \      /  \
an  ulus  e    ic
/ \       / \   / \
e   us    ns  r on  undus
*/
print("Preorder Tree Data ");
// Tree Tree nodes
tree.printPreorder(tree.root);
}
}``````

#### Output

``````Preorder Tree Data
r
om
an
e
us
ulus
ub
e
ns
r
ic
on
undus``````
``````// Kotlin Program for
class TreeNode
{
var label: String;
var child: MutableList < TreeNode > ;
constructor()
{
this.label = "";
this.child = mutableListOf < TreeNode > ();
}
constructor(value: String)
{
this.label = value;
this.child = mutableListOf < TreeNode > ();
}
}
{
var root: TreeNode ? ;
constructor()
{
this.root = TreeNode("");
}
fun matchingCharacters(word: String, node: TreeNode ? ): Int
{
var matches: Int = 0;
var minLength: Int = 0;
if (node!!.label.length >= word.length)
{
minLength = word.length;
}
else if (node.label.length < word.length)
{
minLength = node.label.length;
}
if (minLength > 0)
{
var i: Int = 0;
// Count matches characters
while (i < minLength)
{
if (word.get(i) == node.label.get(i))
{
// When characters are same
matches += 1;
}
else
{
// When characters are not same
return matches;
}
i += 1;
}
}
// Return the current number of matches
return matches;
}
// Add node in proper place
fun insertProcess(word: String, node: TreeNode ? ): Unit
{
val matches: Int = this.matchingCharacters(word, node);
if ((matches == 0) || (node == this.root) ||
((matches > 0) && (matches < word.length) &&
(matches >= node!!.label.length)))
{
var inserted: Boolean = false;
val newWordPart: String = word.substring(matches, word.length);
var i: Int = 0;
while (i < node!!.child.size)
{
if (node.child[i].label.startsWith(
"" + newWordPart.get(0).toString()))
{
inserted = true;
this.insertProcess(newWordPart, node.child[i]);
}
i += 1;
}
if (inserted == false)
{
}
}
else if (matches < word.length)
{
val commonRoot: String = word.substring(0, matches);
val branchPreviouslabel: String = node!!.label.substring(
matches, node.label.length);
val branchNewlabel: String = word.substring(
matches, word.length);
node.label = commonRoot;
val newNodePreviouslabel: TreeNode = TreeNode(
branchPreviouslabel);
var i: Int = 0;
// Add current node child to new node
while (i < node.child.size)
{
i += 1;
}
// Clear node element
node.child.clear();
}
else if (matches > node!!.label.length)
{
val newLabel: String = node.label.substring(
node.label.length, word.length);
}
}
fun insert(word: String): Unit
{
this.insertProcess(word, this.root);
}
// Display the preorder of tree elements
fun printPreorder(node: TreeNode ? ): Unit
{
if (node == null)
{
return;
}
// Display node value
println(node.label);
var i: Int = 0;
while (i < node.child.size)
{
// Visit child node
this.printPreorder(node.child[i]);
i += 1;
}
}
}
fun main(args: Array < String > ): Unit
{
tree.insert("romane");
tree.insert("romanus");
tree.insert("romulus");
tree.insert("rubens");
tree.insert("ruber");
tree.insert("rubicon");
tree.insert("rubicundus");
/*
r
/  \
/    \
/      \
/        \
om        ub
/  \      /  \
an  ulus  e    ic
/ \       / \   / \
e   us    ns  r on  undus
*/
print("Preorder Tree Data ");
// Tree Tree nodes
tree.printPreorder(tree.root);
}``````

#### Output

``````Preorder Tree Data
r
om
an
e
us
ulus
ub
e
ns
r
ic
on
undus``````

## 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.