java-loop inside a recursive method

Question

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?

because i want to iterate through the arraylist in order to call my method on all the nodes. — Number 13
– Number 13, Commented May 14, 2017 at 16:15
@Aominè Why shouldn't he? If you have a tree and you need to recur on every node, I think it's ok to loop through all the children of a given node and recur on each of them — BackSlash
– BackSlash, Commented May 14, 2017 at 16:15
Your for loop has a return statement. Only the first children is visited. — Jose Luis
– Jose Luis, Commented May 14, 2017 at 16:17

Beri · Accepted Answer · 2017-05-14 16:20:29Z

1

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 ;
}

answered May 14, 2017 at 16:20

Beri

11.6k4 gold badges38 silver badges59 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Beri Over a year ago

That is what stack is for. Recursive funnctions may be tricky at beginning, but then they are easy:)

neeranzan · Accepted Answer · 2017-05-14 16:27:48Z

0

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.

answered May 14, 2017 at 16:27

neeranzan

1315 bronze badges

Collectives™ on Stack Overflow

java-loop inside a recursive method

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related