Member Avatar for nisaa15

Hi All,

Im trying to implement a trie in java(which is basically a tree used to store words). I have the following method to add a word but am unsure how i would go about check to see if the prefix of a word already exists. Heres my code:

public void add(String word){
for (int i = 0; i<=word.length(); i++){
char c = word.charAt(i);
if(c==..............(trieEdge(c))){  //unsure about this, should check whether an edge with the character c exists in the ith position.
i++;//should go to the next character and node if an edge exists
}  else{
word.makeEdge(c);
}

//hereafter I check to see if the end of the word has been reached in wich case the makeNode/edge would place a terminal node at the end rather than a normal node.

If anyone can give me suggestions as to how I can check to see if the edge already exists in correspondance to the ith position this will be very much appreciated

Cheers

Edited by happygeek because: fixed formatting
  • 3 Contributors
  • 5 Replies
  • 314 Views
  • 2 Days Discussion Span
  • Latest Post Latest Post by Daishi

Dani AI

Generated

A trie node should explicitly store its outgoing edges (children) and a terminal flag. Start at the root, iterate characters one by one, and for each character either follow the existing child or create it. That answers your original question about "which node to look at": always keep a current node reference that moves down the trie as you consume characters.

Here is a concise, idiomatic Java example (uses a char→Node map so it works for arbitrary character sets):

static class Node {
  Map<Character,Node> children = new HashMap<>();
  boolean isWord = false;
}

public void add(String word) {
  if (word == null) return;
  Node cur = root;
  for (int i = 0; i < word.length(); i++) {
    char c = word.charAt(i);
    cur = cur.children.computeIfAbsent(c, k -> new Node());
  }
  cur.isWord = true;
}

Troubleshooting and alternatives:

  • Normalize input (lowercase, trim) and decide allowed characters up front.
  • If your alphabet is small and fixed (e.g., 'a'–'z'), use Node[] children = new Node[26] and index with c - 'a' for faster, lower‑overhead lookups.
  • HashMap is better for sparse or Unicode keys. TreeMap gives ordered iteration if you need it.
  • Duplicates are harmless — just set isWord = true at the end. Add a contains(String) that walks the same path to verify insertions.
  • For concurrency, synchronize mutations or use concurrent maps.

Notes on the thread: 's startsWith/endsWith are higher-level operations you can implement once the trie traversal is in place. 's two-child example demonstrates node references, but for a trie you generally need a map/array of children rather than exactly two child pointers.

Recommended Answers

All 5 Replies

Member Avatar for server_crash

startsWith(String prefix)
endsWith(String postfix)

Member Avatar for nisaa15

how would i know which node im talking about, i want to do it so that the program checks individual characters rather than prefixes. so i would have to check a nodes children but how can i determine which node the program should look at. It should start by looking at the rott nodes children and if the edge exists here follow the edge to the next node and check to see if the next character is amonst the new nodes children and so forth.

Member Avatar for server_crash

What do you mean you don't know what node to look at?

Member Avatar for nisaa15

What do you mean you don't know what node to look at?

Well I want to start the search from the root node. How can I represent the edges that the node has? once the computer knows if the edge exists if will follow this edge through to it destination node. My problem is - how do I represent the edges one node has?

Member Avatar for Daishi

Well I want to start the search from the root node. How can I represent the edges that the node has? once the computer knows if the edge exists if will follow this edge through to it destination node. My problem is - how do I represent the edges one node has?

Well, if you are using Java, this is pretty darn easy to do. Each node could have a list of node references (or pointers, in other languages) within its structure. For example:

class Node {
    //  Note that this is public for example only, you should write your own setting and accessing methods for the nodes.
    public Node childOne, childTwo;

    public Node() {
        childOne=null;
        childTwo=null;
    }
}

This example class could be a node in a tree. Note that childOne and childTwo are just references to Node objects, and are set to null in the constructor. childOne and childTwo can represent the children of that particular node. Each node will actually represet a sub tree using this method. So, you can just do this in your tree structure:

class Tree {
    public Node root;
}

Of course, you can have more than just two node references in your node class. You could just have one node (which would be a linked list), or you could even have a list of nodes (which would be a full blown tree). For your example you probably want each node to have two child nodes, and create a binary search tree from that. Google would be a good place to start for finding out more.

-Fredric

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.