Given a set of strings str, the task is to print all the joints of the Trie constructed from the given set of strings.
Joints of a Trie is the nodes in a trie that have more than one child.
Examples:
Input:
str = {"cat", "there", "caller",
"their", "calling"}
Output: l, a, e
Explanation:
root
/ \
c t
| |
a h
/ | |
t l e
| | \
l i r
| \ | |
e i r e
| |
r n
|
g
Input:
str = {"Candy", "cat",
"Caller", "calling"}
Output: l, a
Explanation:
root
|
c
|
a
/ | \
l n t
| |
l d
| \ |
e i y
| |
r n
|
g
Approach:
Follow the steps given below to solve the problem:
- Traverse the Trie, and take a currChild variable as zero.
- Increment the currChild by 1, when the current node has a child and while returning from current node check if currChild is greater than 1 or not. If so, print this character or joint. Otherwise, skip to next character.
Below is the implementation of the above approach:
C++
// C++ program to print all the// joints of a Trie constructed// from a given set of strings#include <bits/stdc++.h>using namespace std;#define CHILDREN 26#define MAX 100// Trie nodestruct trie { trie* child[CHILDREN]; bool endOfWord;};// Function will return the// new node(initialized to NULLs)trie* createNode(){ trie* temp = new trie(); temp->endOfWord = false; for (int i = 0; i < CHILDREN; i++) { temp->child[i] = NULL; } return temp;}// Function will insert the// string in a trie recursivelyvoid insertRecursively(trie* itr, string str, int i){ if (i < str.length()) { int index = str[i] - 'a'; if (itr->child[index] == NULL) { // Create a new node itr->child[index] = createNode(); } // Recursive call for insertion // of string insertRecursively(itr->child[index], str, i + 1); } else { // Make the endOfWord true // which represents // the end of string itr->endOfWord = true; }}// Function call to insert a stringvoid insert(trie* itr, string str){ // Function call with // necessary arguments insertRecursively(itr, str, 0);}// Function to check whether the// node is leaf or notbool isLeafNode(trie* root){ return root->endOfWord != false;}// Function to display the Joints of trievoid display(trie* root, trie* itr, char str[], int level){ // Count current child int currChild = 0; for (int i = 0; i < CHILDREN; i++) { // Check for NON NULL child is found // add parent key to str and // call the display function // recursively for child node if (itr->child[i]) { str[level] = i + 'a'; display(root, itr->child[i], str, level + 1); currChild++; } } // Print character if it has more // than 1 child if (currChild > 1 && itr != root) { cout << str[level - 1] << endl; }}// Function call for displaying Jointvoid displayJoint(trie* root){ int level = 0; char str[MAX]; display(root, root, str, level);}// Driver codeint main(){ trie* root = createNode(); vector<string> s = { "geek", "geeky", "neveropen", "gel" }; for (string str : s) { insert(root, str); } displayJoint(root); return 0;} |
Java
// Java program to print all the// joints of a Trie constructed// from a given set of Stringsimport java.util.*;class GFG{static final int CHILDREN = 26;static final int MAX = 100;// Trie nodestatic class trie { trie []child = new trie[CHILDREN]; boolean endOfWord;};// Function will return the// new node(initialized to nulls)static trie createNode(){ trie temp = new trie(); temp.endOfWord = false; for (int i = 0; i < CHILDREN; i++) { temp.child[i] = null; } return temp;}// Function will insert the// String in a trie recursivelystatic void insertRecursively(trie itr, String str, int i){ if (i < str.length()) { int index = str.charAt(i) - 'a'; if (itr.child[index] == null) { // Create a new node itr.child[index] = createNode(); } // Recursive call for insertion // of String insertRecursively(itr.child[index], str, i + 1); } else { // Make the endOfWord true // which represents // the end of String itr.endOfWord = true; }}// Function call to insert a Stringstatic void insert(trie itr, String str){ // Function call with // necessary arguments insertRecursively(itr, str, 0);}// Function to check whether the// node is leaf or notstatic boolean isLeafNode(trie root){ return root.endOfWord != false;}// Function to display the Joints of triestatic void display(trie root, trie itr, char str[], int level){ // Count current child int currChild = 0; for (int i = 0; i < CHILDREN; i++) { // Check for NON null child is found // add parent key to str and // call the display function // recursively for child node if (itr.child[i] != null) { str[level] = (char) (i + 'a'); display(root, itr.child[i], str, level + 1); currChild++; } } // Print character if it has more // than 1 child if (currChild > 1 && itr != root) { System.out.print(str[level - 1] + "\n"); }}// Function call for displaying Jointstatic void displayJoint(trie root){ int level = 0; char []str = new char[MAX]; display(root, root, str, level);}// Driver codepublic static void main(String[] args){ trie root = createNode(); String []s = { "geek", "geeky", "neveropen", "gel" }; for (String str : s) { insert(root, str); } displayJoint(root);}}// This code is contributed by sapnasingh4991 |
Python3
# Python3 program to traverse in bottom up mannerCHILDREN = 26MAX = 100# Trie nodeclass trie: def __init__(self): self.child = [None for i in range(CHILDREN)] # endOfWord is true if the node represents # end of a word self.endOfWord = False# Function will return the new node(initialized to NULLs)def createNode(): temp = trie() return temp# Function will inert the string in a trie recursivelydef insertRecursively(itr, str, i): if(i < len(str)): index = ord(str[i]) - ord('a') if(itr.child[index] == None ): #Create a new node itr.child[index] = createNode(); # Recursive call for insertion of string insertRecursively(itr.child[index], str, i + 1); else: # Make the endOfWord true which represents # the end of string itr.endOfWord = True; # Function call to insert a stringdef insert(itr, str): # Function call with necessary arguments insertRecursively(itr, str, 0); # Function to check whether the node is leaf or notdef isLeafNode(root): return root.endOfWord != False; # Function to display the Joints of triedef display(root, itr, str, level): # Count current child currChild = 0; for i in range(CHILDREN): # Check for NON NULL child is found # add parent key to str and # call the display function # recursively for child node if (itr.child[i]): str[level] = chr(i + ord('a')); display(root, itr.child[i],str, level + 1); currChild += 1 # Print character if it has more # than 1 child if (currChild > 1 and itr != root): print(str[level - 1]) # Function call for displaying Jointdef displayJoint(root): level = 0; str = ['' for i in range(MAX)]; display(root, root, str, level); # Driver codeif __name__=='__main__': root = createNode() s = ["geek", "geeky", "neveropen", "gel"] for str in s: insert(root, str); displayJoint(root) # This code is contributed by rutvik_56 |
C#
// C# program to print all the// joints of a Trie constructed// from a given set of Stringsusing System;class GFG{ static readonly int CHILDREN = 26;static readonly int MAX = 100;// Trie nodeclass trie { public trie []child = new trie[CHILDREN]; public bool endOfWord;};// Function will return the// new node(initialized to nulls)static trie createNode(){ trie temp = new trie(); temp.endOfWord = false; for(int i = 0; i < CHILDREN; i++) { temp.child[i] = null; } return temp;}// Function will insert the// String in a trie recursivelystatic void insertRecursively(trie itr, String str, int i){ if (i < str.Length) { int index = str[i] - 'a'; if (itr.child[index] == null) { // Create a new node itr.child[index] = createNode(); } // Recursive call for insertion // of String insertRecursively(itr.child[index], str, i + 1); } else { // Make the endOfWord true // which represents // the end of String itr.endOfWord = true; }}// Function call to insert a Stringstatic void insert(trie itr, String str){ // Function call with // necessary arguments insertRecursively(itr, str, 0);}// Function to check whether the// node is leaf or notstatic bool isLeafNode(trie root){ return root.endOfWord != false;}// Function to display the Joints of triestatic void display(trie root, trie itr, char []str, int level){ // Count current child int currChild = 0; for(int i = 0; i < CHILDREN; i++) { // Check for NON null child is found // add parent key to str and // call the display function // recursively for child node if (itr.child[i] != null) { str[level] = (char)(i + 'a'); display(root, itr.child[i], str, level + 1); currChild++; } } // Print character if it has more // than 1 child if (currChild > 1 && itr != root) { Console.Write(str[level - 1] + "\n"); }}// Function call for displaying Jointstatic void displayJoint(trie root){ int level = 0; char []str = new char[MAX]; display(root, root, str, level);}// Driver codepublic static void Main(String[] args){ trie root = createNode(); String []s = { "geek", "geeky", "neveropen", "gel" }; foreach(String str in s) { insert(root, str); } displayJoint(root);}}// This code is contributed by Rajput-Ji |
Javascript
<script> // Javascript program to print all the // joints of a Trie constructed // from a given set of Strings let CHILDREN = 26; let MAX = 100; // Trie node class trie { constructor() { } } // Function will return the // new node(initialized to nulls) function createNode(endOfWord) { let temp = new trie(); temp.child = new trie(CHILDREN); temp.endOfWord = endOfWord; for (let i = 0; i < CHILDREN; i++) { temp.child[i] = null; } return temp; } // Function will insert the // String in a trie recursively function insertRecursively(itr, str, i) { if (i < str.length) { let index = str[i].charCodeAt() - 'a'.charCodeAt(); if (itr.child[index] == null) { // Create a new node itr.child[index] = createNode(false); } // Recursive call for insertion // of String insertRecursively(itr.child[index], str, i + 1); } else { // Make the endOfWord true // which represents // the end of String itr.endOfWord = true; } } // Function call to insert a String function insert(itr, str) { // Function call with // necessary arguments insertRecursively(itr, str, 0); } // Function to check whether the // node is leaf or not function isLeafNode(root) { return root.endOfWord != false; } // Function to display the Joints of trie function display(root, itr, str, level) { // Count current child let currChild = 0; for (let i = 0; i < CHILDREN; i++) { // Check for NON null child is found // add parent key to str and // call the display function // recursively for child node if (itr.child[i] != null) { str[level] = String.fromCharCode(i + 'a'.charCodeAt()); display(root, itr.child[i], str, level + 1); currChild++; } } // Print character if it has more // than 1 child if (currChild > 1 && itr != root) { document.write(str[level - 1] + "</br>"); } } // Function call for displaying Joint function displayJoint(root) { let level = 0; let str = new Array(MAX); display(root, root, str, level); } let root = createNode(false); let s = [ "geek", "geeky", "neveropen", "gel" ]; for (let str = 0; str < s.length; str++) { insert(root, s[str]); } displayJoint(root);// This code is contributed by mukesh07.</script> |
Output
k e
Time Complexity: time complexity of this implementation is O(V + S), where S is the total number of characters in all the strings in the trie. This makes it suitable for tries with a large number of strings and a moderate number of nodes.
Auxiliary Space: The auxiliary Space of this implementation is O(V), where V is the number of nodes in the trie. This is because the trie uses an array of size 26 to store the children of each node, and each node consumes a constant amount of space.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
