CODEWITHSUNDEEP
javarecursion
rednax
rednax

Reputation: 23

Java Recursion iterator with my own tree

I have two pieces of code that in my mind do the same thing but it doesn't. I am trying to create an iterator for my custom set tree. Here's the code.

public LinkedList<AnyType> traverse (TheNode<AnyType> node,LinkedList<AnyType> theList){ 
    if (node.left != null)
        return traverse (node.left,theList);        
    theList.push(node.element);
    if (node.right != null)
        return traverse (node.right,theList);       

    return theList;

}

public void traverseNrTwo (TheNode<AnyType> node){ 
    if (node.left != null){
        traverseNrTwo (node.left);
    }
    list.push(node.element);
    if (node.right != null){
        traverseNrTwo (node.right);
    }
}

traverse only goes through the left side of the tree and adds it to the list but traveseNrTwo goes through the whole tree. So, my question is, why do they do two different things?

Upvotes: 2

Views: 743

Answers (1)

Eran
Eran

Reputation: 393781

You shouldn't return the result of the recursive calls, since it causes the recursion to visit just the left side of the tree.

public LinkedList<AnyType> traverse (TheNode<AnyType> node,LinkedList<AnyType> theList){ 
    if (node.left != null)
        traverse (node.left,theList); // if you return traverse(node.left,theList) here,
                                      // you end the recursion without adding the current
                                      // node and visiting the right sub-tree 
    theList.push(node.element);
    if (node.right != null)
        traverse (node.right,theList);       

    return theList;   
}

Also note that since you are passing the LinkedList<AnyType> as an argument to your method (i.e. you are not creating a new LinkedList instance inside your method), you don't have to return it. You can simply change the return type to void.

Upvotes: 4

Related Questions