CODEWITHSUNDEEP
javaarraylisttree
PumpkinBreath
PumpkinBreath

Reputation: 915

Traversing a tree that has an arraylist containing an arbitrary number of sub-trees as its children

I am doing some exam revision and found this question on a past exam paper:

enter image description here

enter image description here

Firstly, would anybody ever implement a tree like this or is it simply a an exam problem?

Secondly, I am really confused about how to go about this. I wanted to use BFS or DFS but they only work for binary trees and I'm not very good with recursion so have struggled there as well.

I have come up with this which works but its really ugly and won't work for a general case, only this particular tree:

public ArrayList<Integer> getLeafValues() {
    ArrayList<Integer> leafList = new ArrayList<>();
    Tree current = this;
    for (Tree t : current.children) {
        if (t.children.isEmpty()) {
            leafList.add(t.data);
        } else {
            for (Tree t2 : t.children) {
                if (t2.children.isEmpty()) {
                    leafList.add(t2.data);
                } else {
                    for (Tree t3 : t2.children) {
                        if (t3.children.isEmpty()) {
                            leafList.add(t3.data);
                        }
                    }
                }
            }
        }
    }
    return leafList;
}

Any help on this would be great, as I said before its exam revision, not homework. Thanks

Upvotes: 1

Views: 146

Answers (1)

Eran
Eran

Reputation: 393851

Such problems can be solved with recursion:

public ArrayList<Integer> getLeafValues() {
    ArrayList<Integer> leafList = new ArrayList<>();
    getLeaves (this, leafList);
    return leafList;
}

public void getLeaves (Tree current, List<Integer> leafList)
{
    if (current.children.isEmpty()) {
        leafList.add(current.data);
    } else {
        for (Tree t : current.children) {
            getLeaves (t, leafList);
        }
    }
}

The recursion ends when you reach a leaf (i.e. a Tree without children), in which case you add that leaf to the List.

If the current node has children, you call the method recursively on all the children, to collect the leaves of their sub-trees.

Upvotes: 1

Related Questions