CODEWITHSUNDEEP
javarecursiontree
doddy
doddy

Reputation: 619

Recursively search through a Tree in Java

I have a non-binary Tree with nodes defined in the following way:

public class TreeNode{
private String label;
private TreeNode[] children;

public TreeNode(String label){
     this.label = label;
     children = new TreeNode[9]
}

So each node has a label and an array of size 9 which holds its 9 children. Now in my tree class, I want to define a find method that will find a node with a specific label. This is what I could come up with:

public TreeNode find(String label, TreeNode node) {
    TreeNode result = null;
    if (node.getLabel().equals(label)) {
        return node;
    } else {
        if (node.hasChildren()){
            for (int i = 0; i< node.getChildren().length; i++){
                if (node.getChildren()[i].getLabel().equals(label)) {
                    result = node.getChildren()[i];
                    break;
                else
                    return find(label, node.getChildren()[i];
           }
    return result;
}

And the problem with this is that it just goes a level deeper everytime without looking through the siblings of the "node" I provide to the method.

I'm sure the solution is trivial but I just can't seem to catch it.

There is a similar question here and I think their issue is also similar but I can't seem to translate the provided solution to my application.

What am I missing? Thank you for your help!

Upvotes: 1

Views: 8781

Answers (1)

cs95
cs95

Reputation: 403198

You shouldn't use return inside the for loop without checking the returned value of the recursive call. Also, apply the recursive call to all items in the loop unconditionally.

for (int i = 0; i < node.getChildren().length; i++){
    result = find(label, node.getChildren()[i];
    if(result != null) {
        return result;
    }
}

Upvotes: 2

Related Questions