Simple recursion function to save values to List

Question

This question relates to recursion. Consider the program shown below (not my real code, but this explains the problem I have).

The function must use recursion as shown, and what I want to do is have a way that each leaf value instead of getting printed out, is saved to a list. So finally I get a List<String> that when I print out gives me the contents of each leaf node.

String xml = "<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n" +
"<title text=\"title1\">\n" +
"    <comment id=\"comment1\">\n" +
"        <data> abcd </data>\n" +
"        <data> efgh </data>\n" +
"    </comment>\n" +
"    <comment id=\"comment2\">\n" +
"        <data> ijkl </data>\n" +
"        <data> mnop </data>\n" +
"        <data> qrst </data>\n" +
"    </comment>\n" +
"</title>\n";

DocumentBuilder builder = DocumentBuilderFactory.newInstance().newDocumentBuilder();
Document doc = builder.parse(new InputSource(new StringReader(xml)));

List<String> results = traverse(doc.getFirstChild());

//Want to print out results list here...

public static List<String> traverse(Node node){
    System.out.println(node.getNodeName());
    for(int i = 0; i < node.getChildNodes().getLength(); i++){
        traverse(node.getChildNodes().item(i));         
    }
    return null;
}

So my question is, how can I re-write the traverse function in a way that, it still uses recursion but saves all leaf nodes to the list. And then it returns the list of all values.

Does "must use recursion" imply this is homework? (This wouldn't be a problem, but I would retag the question accordingly) — Shlublu
– Shlublu, Commented Aug 29, 2011 at 14:44
Did you even try anything? There is not even much to do! Don't expect this site to give you code withouth trying first... — f1sh
– f1sh, Commented Aug 29, 2011 at 14:45
I want to re-write the traverse function, in a way that it still uses recursion, but saves all leaf nodes to the list, and then returns the list of all values. — Larry
– Larry, Commented Aug 29, 2011 at 14:45
I have tried a lot, and this is not homework. See some of my previous questions, I need to use recursion for to be able to properly transform an xml document into a table. — Larry
– Larry, Commented Aug 29, 2011 at 14:46

CaNNaDaRk · Accepted Answer · 2011-08-29 17:29:28Z

2

This one stores in a List the same Strings you print with your traverse function and you don't need to pass the List as an argument:

public static List<String> traverse( Node node ) {
        List<String> results = new LinkedList();
        results.add(node.getNodeName());
        if ( node.getChildNodes().getLength() > 0 ) {
            for ( int i = 0; i < node.getChildNodes().getLength(); i++ )
                results.addAll(traverse(node.getChildNodes().item(i)));
        }
        return results;
    }

edited Aug 29, 2011 at 17:29

answered Aug 29, 2011 at 15:04

CaNNaDaRk

1,32112 silver badges20 bronze badges

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

6 Comments

Larry Over a year ago

thanks, this was the solution I was looking for. Actually it was similar to what I had, but I noticed I had another bug. Apparently, if the List is of some other object type, you need to add a new object to the list, not the recurring one!

Kevin Over a year ago

I thought you said you wanted the contents of the list to contain each leaf node. This gives you a list with all nodes.

Larry Over a year ago

@Kevin that’s true... but the main thing I was after was a way to store the recursive data in a list. I guess the real solution is a mix between yours and this one, but I side with this since I like the way it does not modify the function signature, whereas yours does.

CaNNaDaRk Over a year ago

You can filter the Strings you add to the list by simply adding an IF before "results.add(node.getNodeName());" so that you can check if the node is a #text node and then add it's child value; this way the function still works and you can have leaf nodes only.

Kevin Over a year ago

@Larry: It's not the problem you think it is. See my updated answer. I think it's a bit sloppy to allocate a new linked list for every node in the xml tree as in this solution.

|

Thomas · Accepted Answer · 2011-08-29 14:47:57Z

0

You could either return a list and add the elements from the recursive calls to the result list of the current call or pass the list as a parameter and add the result directly.

answered Aug 29, 2011 at 14:47

Thomas

88.9k13 gold badges126 silver badges162 bronze badges

Comments

Kevin · Accepted Answer · 2011-08-29 18:34:13Z

0

I think what you want is something like this:

public static void traverse(Node node, List<String> results) {
    if (node.getChildNodes().getLength() == 0) {
        // leaf node
        results.add(node.getNodeValue());
    }
    else {
        // walk all children
        for (int i = 0; i < node.getChildNodes().getLength(); i++) {
            traverse(node.getChildNodes().item(i));
        }
    }
}
public static List<String> traverse(Node node) {
    List<String> result = new LinkedList<String>();
    traverse(node,result);
    return result;
}

edited Aug 29, 2011 at 18:34

answered Aug 29, 2011 at 14:47

Kevin

25.3k20 gold badges107 silver badges159 bronze badges

Collectives™ on Stack Overflow

Simple recursion function to save values to List

3 Answers 3

6 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

6 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related