Display trie tree elements

In computer science, a trie is a tree-like data structure used to store a dynamic set of strings, where each node represents a single character. Tries are commonly used in applications involving text processing, such as autocomplete suggestions, spell checking, and IP routing. One common task with a trie is to display all the elements it contains.

Problem Statement

Given a Trie data structure with strings inserted into it, the task is to display all the elements (strings) present in the Trie.

Example

Consider the following Trie structure:

    root
    /  \  \
   c    d  r 
   |    |  |
   o    o  u
   | \  |  |
   d  w g  n
   |  
   e

The strings inserted into this Trie are: "run", "code", "dog", and "cow". The goal is to display these strings in lexicographic (alphabetical) order.

Idea to Solve

To solve this problem, we can perform a depth-first traversal of the Trie starting from the root node. During traversal, we can keep track of the current prefix formed by the characters encountered so far. When we reach a node that marks the end of a string, we print the current prefix to display the complete word.

Pseudocode

display(node, currentPrefix):
    if node is null:
        return
    if node.end is true:
        print currentPrefix
    for i from 0 to ALPHABETS - 1:
        if node.children[i] is not null:
            display(node.children[i], currentPrefix + character(i))

Algorithm Explanation

1. Start at the root node of the Trie.
2. Initialize an empty string called currentPrefix.
3. Traverse through each child of the current node.
4. For each child, recursively call the display function with the child node and the updated currentPrefix by adding the corresponding character.
5. If the current node marks the end of a string (i.e., end is true), print the currentPrefix.
6. Repeat steps 3-5 for each child of the current node.
7. Continue the traversal until all paths in the Trie have been explored.

Code Solution

• C++
• Java
• Python
• C#
• Ruby
• Php
• Node Js

/*
C++ program
Trie Display Elements
*/
#include <iostream>

#include <string.h>

#define ALPHABETS 26

using namespace std;
class Node {
  public:
  bool end;
  Node *children[ALPHABETS];
  Node() {
    this->end = false;
    for (int i = 0; i < ALPHABETS; ++i) {
      this->children[i] = NULL;
    }
  }
};
class Trie {
  public:
    Node *root;
  Trie() {
    this->root = new Node();
  }
  void insert(string text) {
    int length = text.size();
    int index = 0;
    Node *head = this->root;
    int level = 0;
    while (level < length) {
      index = text[level] - 'a';
      if (head->children[index] == NULL) {
        head->children[index] = new Node();
      }
      head = head->children[index];
      level++;
    }
    if (head != NULL) {
      head->end = true;
    }
  }
  void display(Node *head, string about) {
    if (head != NULL) {
      if (head->end == true) {
        cout << about<<endl;
      }
      for (int i = 0; i < ALPHABETS; i++) {
        if (head->children[i] != NULL) {
          this->display(head->children[i], about + ((char)(i + 97)));
        }
      }
    }
  }
};
int main() {
  
  Trie obj;
  /*
    root
   /  \  \
  c    d  r 
  |    |  |
  o    o  u
  | \  |  |
  d  w g  n
  |  
  e  
  
  */
 
  obj.insert("run");
  obj.insert("code");
  obj.insert("dog");
  obj.insert("cow");
  obj.display(obj.root, "");
  return 0;
}

code
cow
dog
run

/*
  Java program
  Trie Display Elements
*/
class Node {
  //Indicates end of string
  public boolean end;

  public Node[] children;

  public Node(int size) {
    end = false;
    children = new Node[size];
  }
}
public class Trie {
  
  public int ALPHABETS = 26;


  public Node root;

  public Trie() {
    root = new Node(ALPHABETS);
  }

  public void insert(String text) {
    //First get the length of text
    int length = text.length();

    //This variable are used to task find the index location of character
    int index = 0;

    //Get the root node
    Node head = root;

    for (int level = 0; level < length; level++) {
      //Get the index
      index = text.charAt(level) - 'a';

      if (head.children[index] == null) {
        //When need to add new Node
        head.children[index] = new Node(ALPHABETS);
      }

      head = head.children[index];
    }
    if (head != null) {
      //Indicates end of string
      head.end = true;
    }
  }
  public void display(Node head, String about) {

    if (head != null) {

      if (head.end == true) {
        System.out.println(about);
      }

      for (int i = 0; i < ALPHABETS; i++) {
        if (head.children[i] != null) {
          display(head.children[i], about + ((char)(i + 97)));
        }
      }
    }
  }

  public static void main(String[] args) {
    //Make object
    Trie obj = new Trie();
    /*
      root
     /  \  \
    c    d  r 
    |    |  |
    o    o  u
    | \  |  |
    d  w g  n
    |  
    e  
    
    */
    obj.insert("run");
    obj.insert("code");
    obj.insert("dog");
    obj.insert("cow");
    obj.display(obj.root, "");
  }
}

code
cow
dog
run

# Python 3 Program
# Trie Display Elements
class Node :

  def __init__(self, size) :
    self.end = False
    self.children = [None]*size
  

class Trie :

  def __init__(self) :
    self.ALPHABETS = 26
    self.root = Node(self.ALPHABETS)
  
  def insert(self, text) :
    length = len(text)
    index = 0
    head = self.root
    level = 0
    while (level < length) :
      index = ord(text[level]) - ord('a')
      if (head.children[index] == None) :
        head.children[index] = Node(self.ALPHABETS)
      
      head = head.children[index]
      level += 1
    
    if (head != None) :
      head.end = True
    
  
  def display(self, head, about) :
    if (head != None) :
      if (head.end == True) :
        print(about)
      
      i = 0
      while (i < self.ALPHABETS) :
        if (head.children[i] != None) :
          self.display(head.children[i], about + (chr(i + 97)))
        
        i += 1
      
    
  
def main() :
  obj = Trie()
  
  #      root
  #     /  \  \
  #    c    d  r
  #    |    |  |
  #    o    o  u
  #    | \  |  |
  #    d  w g  n
  #    |
  #    e  

  obj.insert("run")
  obj.insert("code")
  obj.insert("dog")
  obj.insert("cow")
  obj.display(obj.root, "")
  

if __name__ == "__main__":
  main()

code
cow
dog
run

/*
C# program
Trie Display Elements
*/
using System;
public class Node {
	//Indicates end of string
	public Boolean end;

	public Node[] children;

	public Node(int size) {
		end = false;
		children = new Node[size];
	}
}
public class Trie 
{ 
	public int ALPHABETS = 26;

	public Node root;

	public Trie() {
		root = new Node(ALPHABETS);
	}

	public void insert(String text) {
		//first get the.Length of text
		int size = text.Length;

		//This variable are used to task find the index location of character
		int index = 0;

		//get the root node
		Node head = root;

		for (int level = 0; level < size; level++) {
			//Get the index
			index = text[level] - 'a';

			if (head.children[index] == null) {
				//When need to add new Node
				head.children[index] = new Node(ALPHABETS);
			}

			head = head.children[index];
		}
		if (head != null) {
			//indicates end of string
			head.end = true;
		}
	}
	public void display(Node root, String about) {

		if (root != null) {

			if (root.end == true) {
				Console.WriteLine(about);
			}

			for (int i = 0; i < ALPHABETS; i++) {
				if (root.children[i] != null) {
					display(root.children[i], about + ((char)(i + 97)));
				}
			}
		}
	}


	public static void Main(String[] args) 
	{
		//Make object
		Trie obj = new Trie();
		/*
      root
     /  \  \
    c    d  r 
    |    |  |
    o    o  u
    | \  |  |
    d  w g  n
    |  
    e  
    
    */
		obj.insert("run");
		obj.insert("code");
		obj.insert("dog");
		obj.insert("cow");
		obj.display(obj.root, "");
	}
}

code
cow
dog
run

# Ruby program
# Trie Display Elements

class Node
	attr_reader :end, :children
	attr_accessor :end, :children
	def initialize(size) 
		@end = false
		@children = Array.new(size){nil}
	end
end

class Trie
	attr_reader :ALPHABETS, :root
	attr_accessor :ALPHABETS, :root
	def initialize() 
		@ALPHABETS = 26
		@root = Node.new(@ALPHABETS)
	end
	def insert(text) 
		size = text.length
		location = 0
		head = @root
		level = 0
		while (level < size) 
			location = text[level].ord - 'a'.ord
			if (head.children[location] == nil) 
				head.children[location] = Node.new(@ALPHABETS)
			end
			head = head.children[location]
			level += 1
		end
		if (head != nil) 
			head.end = true
		end
	end
	def display(head, about) 
		if (head != nil) 
			if (head.end == true) 
				print(about,"\n")
			end
			i = 0
			while (i < @ALPHABETS) 
				if (head.children[i] != nil) 
					self.display(head.children[i], about + ((i + 97).chr))
				end
				i += 1
			end
		end
	end
end

def main() 
	obj = Trie.new()

	#      root
	#     /  \  \
	#    c    d  r
	#    |    |  |
	#    o    o  u
	#    | \  |  |
	#    d  w g  n
	#    |
	#    e  

	obj.insert("run")
	obj.insert("code")
	obj.insert("dog")
	obj.insert("cow")
	obj.display(obj.root, "")
end
main()

code
cow
dog
run

<?php
/*
Php Program
Trie Display Elements
*/
class Node {
  public $end;
  public $children = [];

  function __construct($size) {
    $this->end = false;
    $this->children = array_fill(0, $size, null);
  }
}
class Trie {
  private $ALPHABETS;
  public $root;

  function __construct() {
    $this->ALPHABETS = 26;
    $this->root = new Node($this->ALPHABETS);
  }

  public  function insert($text) {
    $size = strlen($text);
    $index = 0;
    $head = $this->root;
    $level = 0;
    while ($level < $size) {
      $index =  ord($text[$level]) - ord('a');
      if ($head->children[$index] == null) {
        $head->children[$index] = new Node($this->ALPHABETS);
      }
      $head = $head->children[$index];
      $level++;
    }
    if ($head != null) {
      $head->end = true;
    }
  }
  public  function display($head, $about) {
    if ($head != null) {
      if ($head->end == true) {
        echo $about."\n";
      }
      $i = 0;
      while ($i < $this->ALPHABETS) {
        if ($head->children[$i] != null) {
          $this->display($head->children[$i], $about . (chr($i + 97)));
        }
        $i++;
      }
    }
  }
}

function main() {
 
  $obj = new Trie();
  /*
      root
     /  \  \
    c    d  r 
    |    |  |
    o    o  u
    | \  |  |
    d  w g  n
    |  
    e  
    
  */

  $obj->insert("run");
  $obj->insert("code");
  $obj->insert("dog");
  $obj->insert("cow");
  $obj->display($obj->root, "");
}
main();

code
cow
dog
run

/*
  Node Js Program
  Trie Display Elements
*/
class Node {
	
	constructor(size) {
		this.end = false;
		this.children = new Array(size).fill(null);
	}
}
class Trie {
	
	constructor() {
		this.ALPHABETS = 26;
		this.root = new Node(this.ALPHABETS);
	}
	insert(text) {
		var size = text.length;
		var index = 0;
		var head = this.root;
		var level = 0;
		while (level < size) {
			index = text.charCodeAt(level) - 'a'.charCodeAt(0);
			if (head.children[index] == null) {
				head.children[index] = new Node(this.ALPHABETS);
			}
			head = head.children[index];
			level++;
		}
		if (head != null) {
			head.end = true;
		}
	}
	display(head, about) {
		if (head != null) {
			if (head.end == true) {
				console.log(about);
			}
			var i = 0;
			while (i < this.ALPHABETS) {
				if (head.children[i] != null) {
					this.display(head.children[i], about + (String.fromCharCode(i + 97)));
				}
				i++;
			}
		}
	}



}
function main() {
	var obj = new Trie();
    /*
      root
     /  \  \
    c    d  r 
    |    |  |
    o    o  u
    | \  |  |
    d  w g  n
    |  
    e  
    
    */
    obj.insert("run");
    obj.insert("code");
    obj.insert("dog");
    obj.insert("cow");
    obj.display(obj.root, "");
}
main();

code
cow
dog
run

Time Complexity Analysis

In the Trie, each character is stored in a separate node, and each node has a fixed number of children (in this case, 26 for the English alphabet). Therefore, the time complexity of the display function depends on the number of nodes in the Trie. Let's denote the total number of nodes as N.

During the traversal, each node is visited once, and each visit involves a constant amount of work. Hence, the time complexity of the display function is O(N), where N is the total number of nodes in the Trie.