Radix tree implementation

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
// Radix tree insert
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 class RadixTree
{
    public TreeNode root;
    public RadixTree()
    {
        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)
            {
                // Add new part
                node.child.add(new TreeNode(newWordPart));
            }
        }
        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)
            {
                newNodePreviouslabel.child.add(node.child.get(i));
            }

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

            // Add new node
            node.child.add(newNodePreviouslabel);

            // Add branch new label
            node.child.add(new TreeNode(branchNewlabel));
        }
        else if (matches > node.label.length())
        {
            String newLabel = node.label.substring(
              node.label.length(), word.length());
            
            // Add new label
            node.child.add(new TreeNode(newLabel));
        }
    }
    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)
    {
        RadixTree tree = new RadixTree();
        // Add tree node
        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
// Radix tree insert
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
}

type RadixTree struct {
    root * TreeNode
}
func getRadixTree() * RadixTree {
    var me *RadixTree = &RadixTree {}
    me.root = getTreeNode("")
    return me
}
func(this RadixTree) matchingCharacters(word string, 
    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 {
            // Add new part
            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
        // Add new node
        node.child = append(node.child, newNodePreviouslabel)
        // Add branch new label
        node.child = append(node.child, getTreeNode(branchNewlabel))
    } else if matches > len(node.label) {
        var newLabel string = node.label[len(node.label) : len(word)]
        // Add new label
        node.child = append(node.child, getTreeNode(newLabel))
    }
}
func(this RadixTree) insert(word string) {
    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() {
    var tree * RadixTree = getRadixTree()
    // Add tree node
    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
// Radix tree insert
class TreeNode
{
    public: string label;
    vector < TreeNode *> child; 
    TreeNode(){
        this->label = "";
    }
    TreeNode(string value)
    {
        this->label = value;
    }
};
class RadixTree
{
    public: TreeNode *root;
    RadixTree()
    {
        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)
            {
                // Add new part
                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();
            // Add new node
            node->child.push_back(newNodePreviouslabel);
            // Add branch new label
            node->child.push_back(new TreeNode(branchNewlabel));
        }
        else if (matches > node->label.length())
        {
            string newLabel = 
              node->label.substr(node->label.length(), word.length());
            // Add new label
            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()
{
    RadixTree *tree = new RadixTree();
    // Add tree node
    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
// Radix tree insert
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 class RadixTree
{
    public TreeNode root;
    public RadixTree()
    {
        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)
            {
                // Add new part
                node.child.Add(new TreeNode(newWordPart));
            }
        }
        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)
            {
                newNodePreviouslabel.child.Add(node.child[i]);
            }
            // Clear node element
            node.child.Clear();
            // Add new node
            node.child.Add(newNodePreviouslabel);
            // Add branch new label
            node.child.Add(new TreeNode(branchNewlabel));
        }
        else if (matches > node.label.Length)
        {
            String newLabel = node.label.Substring(node.label.Length, word.Length);
            // Add new label
            node.child.Add(new TreeNode(newLabel));
        }
    }
    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)
    {
        RadixTree tree = new RadixTree();
        // Add tree node
        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
// Radix tree insert
class TreeNode
{
    public $label;
    public $child;

    public  function __construct($value)
    {
        $this->label = $value;
        $this->child = array();
    }
}
class RadixTree
{
    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)
            {
                // Add new part
                $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();
            // Add new node
            $node->child[] = $newNodePreviouslabel;
            // Add branch new label
            $node->child[] = new TreeNode($branchNewlabel);
        }
        else if ($matches > strlen($node->label))
        {
            $newLabel = substr($node->label, 
                strlen($node->label), 
                strlen($word) - strlen($node->label));
            // Add new 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 = new RadixTree();
    // Add tree node
    $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
// Radix tree insert
class TreeNode
{

    constructor(value)
    {
        this.label = value;
        this.child =  [];
    }
}
class RadixTree
{
    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)
            {
                // Add new part
                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 = [];
            // Add new node
            node.child.push(newNodePreviouslabel);
            // Add branch new label
            node.child.push(new TreeNode(branchNewlabel));
        }
        else if (matches > node.label.length)
        {
            var newLabel = node.label.substring(
                node.label.length, word.length);
            // Add new label
            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()
{
    var tree = new RadixTree();
    // Add tree node
    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
#  Radix tree insert
class TreeNode :
    def __init__(self) :
        self.label = ""
        self.child = []
    
    def __init__(self, value) :
        self.label = value
        self.child = []
    

class RadixTree :
    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) :
                #  Add new part
                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()
            #  Add new node
            node.child.append(newNodePreviouslabel)
            #  Add branch new label
            node.child.append(TreeNode(branchNewlabel))
        elif (matches > len(node.label)) :
            newLabel = node.label[len(node.label): len(word)]
            #  Add new label
            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 = RadixTree()
    #  Add tree node
    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
#  Radix tree insert
class TreeNode 
    # Define the accessor and reader of class TreeNode
    attr_reader :label, :child
    attr_accessor :label, :child
    def initialize() 
        self.label = ""
        self.child = []
    end

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

end

class RadixTree 
    # Define the accessor and reader of class RadixTree
    attr_reader :root
    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) 
                #  Add new part
                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()
            #  Add new node
            node.child.push(newNodePreviouslabel)
            #  Add branch new label
            node.child.push(TreeNode.new(branchNewlabel))
        elsif (matches > node.label.length) 
            newLabel = node.label[node.label.length...word.length]
            #  Add new label
            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 = RadixTree.new()
    #  Add tree node
    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
// Radix tree insert
class TreeNode(var label: String,
    var child: ArrayBuffer[TreeNode])
{
    def this()
    {
        this("", new ArrayBuffer[TreeNode]())
    }
    def this(value: String)
    {
        this(value, new ArrayBuffer[TreeNode]())
    }
}
class RadixTree(var root: 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)
            {
                // Add new part
                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();
            // Add new node
            node.child += newNodePreviouslabel;
            // Add branch new label
            node.child += new TreeNode(branchNewlabel);
        }
        else if (matches > node.label.length())
        {
            var newLabel: String = node.label.substring(
              node.label.length(), word.length());
            // Add new label
            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 = {
        var tree: RadixTree = new RadixTree();
        // Add tree node
        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
// Radix tree insert
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 > ();
    }
}
class RadixTree
{
    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)
            {
                // Add new part
                node.child.add(TreeNode(newWordPart));
            }
        }
        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)
            {
                newNodePreviouslabel.child.add(node.child[i]);
                i += 1;
            }
            // Clear node element
            node.child.clear();
            // Add new node
            node.child.add(newNodePreviouslabel);
            // Add branch new label
            node.child.add(TreeNode(branchNewlabel));
        }
        else if (matches > node!!.label.length)
        {
            val newLabel: String = node.label.substring(
              node.label.length, word.length);
            // Add new label
            node.child.add(TreeNode(newLabel));
        }
    }
    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
{
    val tree: RadixTree = RadixTree();
    // Add tree node
    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

« Previous Next »

Tree

AVL Tree Insertion

AVL Tree Deletion

AVL tree with duplicate key

Splay tree insertion

Splay tree deletion

Trie insertion

Display trie tree elements

Trie Deletion

Trie Search Word Element

Trie Bottom Up Traversal

Count Total words in Trie

Red Black Tree insertion

Red Black tree node deletion

Find duplicate rows in a binary matrix

Find the longest common prefix using Trie

Find a longest length word in Trie

Implement Leftist Tree

Fenwick Tree

Pattern Searching in Trie tree

B Tree node insertion

K dimensional tree insertion

Find the minimum in K dimensional tree

Node deletion in K dimensional tree

Construct segment tree from array

Segment tree update query

Implement B + Tree

N ary tree implementation

Find the all Kth ancestor nodes in an N-ary tree

Print the all leaf nodes in N-ary tree

Find height of n-ary tree

Minimum value node having maximum depth in an N-ary Tree

Replace every node with depth in n-ary tree

Treap implementation

Implement interval tree

Ternary Search Tree Insertion

Huffman Tree Example

Ternary Search Tree Deletion

Suffix tree implementation

Score of parentheses using tree

Construct N Level Calkin-Wilf Tree

Sort array with repeated element using AVL Tree

Count the number of words with given prefix using Trie

Find shortest unique prefix for every word in a given list

Iterative n-ary tree preorder traversal

Level order traversal of n-ary tree

Post order traversal of n-ary tree

Remove all leaf nodes from an n-ary tree

Difference between sums of odd and even levels in n-ary tree

Sum of all leaf nodes from a N-ary Tree

Radix tree implementation

Implementation trie tree with memory optimization

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

Name