CODEWITHSUNDEEP
java
Number 13
Number 13

Reputation: 45

java-loop inside a recursive method

I have a class called TrieNode which has a char key and arrayList of triNode. I am trying to implement a trie.

Structure :

something like this

For example the root key is '.' and the children are t,o,s, and p. for the node with key 's', the children are t and p. I want to calculate the number of nodes in the trie. i used this algorithm 

public int size(TrieNode tmp, int n){

    if(tmp.children.isEmpty()){
        return 0;
    }

    for(int i=0;i<tmp.children.size();i++){
        return 1 + size(tmp.children.get(i), n);
    }


    return 1;
}

the problem is i is not unique for each call. so the method is called on the root then s then it child t then t then o until p. when it returns to s again it doesn't call the method on p.

how to fix this?

Upvotes: 1

Views: 1180

Answers (2)

neeranzan
neeranzan

Reputation: 131

Use DFS for this algorithm. Every node you visited is a child node. Sum up the count after you visit that child node. Do something like this..

//the root is the first node to be passed on.**
void size(TrieNode node){
if(node is null) return;
if(node is not null) result.add(node);

 while(there exist childNode in node){
   size(childNode);
}
}

Result is an ArrayList containing all the nodes of tree. result.size() gives you the number of nodes in tree.

Upvotes: 0

Beri
Beri

Reputation: 11600

The problem is that you exit the loop for the first element. If you want to sum all the elements, then you need to sum the recursive results before returning to parent.

public int size(TrieNode tmp, int n){

    int sum = 0;
    for(int i=0;i<tmp.children.size();i++){
        sum +=  size(tmp.children.get(i), n);
    }

    if(/* node has char n */){
      return sum + 1;
    }
    return sum ;
}

Upvotes: 1

Related Questions