Iteratively traverse through tree to find size

Question

I need to find the number of elements in a tree using an iterative algorithm, but I'm finding the code conceptually very difficult to write.

My approach is to start at the root node and visit the child nodes, then the children of these child nodes, and so on.

This is the code I've written which works for a small tree, but isn't a real solution because I'd need to add an additional block for each level of depth:

// Start the counter at 1 because the root node counts
int size = 1;

for(ITree child1 : root) {
    size++;
    for(ITree child2 : child1) {
        size++;
        for(ITree child3 : child2) {
            size++;
            for(ITree child4 : child3) {
                size++;
                for(ITree child5 : child4) {
                    size++;
                }
            }
        }
    }
}
return size;

Answer 1

Conceptually, keep a stack (LinkedList, etc.). For each child (now, your child loops), add to the stack. Continue looping through the stack until it is finally empty.

This isn't tested, but this should do exactly what you're looking for. I'm just using java.io.File instead of your "ITree", as it's something I can compile against:

int sizeOfTree(File root){
    // Start the counter at 1 because the root node counts

    int size = 1;

    LinkedList<File> stack = new LinkedList<File>();
    stack.add(root);

    while(!stack.isEmpty()){
        File f = stack.remove();
        for(File child : f.listFiles()){
            size++;
            stack.add(child);
        }
    }

    return size;
}

Answer 2

Using a recursive data structure

It is not practically possible to iteratively traverse a recursive data structure, like a tree with pointers - this is because of the fact that the objects "hide" their underlying data elements.

Using a different data structure

All trees can be stored/implemented as to linear, array data structures, where indices can be calculated using exponential mathematics :

For example, a tree [0, 1, 2, 3, null, 4,null] would describe a tree with 0 at the root, where 0 had direct children 1 and 2. And then 1 has left child "3", and 2 has left child "4".

Thus, if you store the tree this way, the number of elements is, naturally, the number of non-null elements in the array.

Put more simply : Store the tree in a linear structure , and you can know the length at any given time without having to make any kind of fancy algorithm.