Cross the tree iteratively to find the size

Question

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

My approach is to start from the root of the node and visit the child nodes, then the child nodes, etc.

This is the code I wrote that works for a small tree, but is not a real solution, because I need to add an extra block for each depth level:

// 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 hold the stack (LinkedList, etc.). For each child (now, your child’s loops) add to the stack. Continue to scroll through the stack until it becomes empty.

This is not tested, but it should do exactly what you are looking for. I just use java.io.File instead of your “ITree”, as I can compile it:

 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 impossible to iteratively traverse a recursive data structure, like a tree with pointers - this is because objects “hide” their underlying data elements.

Using a different data structure

All trees can be stored / implemented as linear, massive data structures, where indexes can be calculated using exponential mathematics:

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

Thus, if you store the tree in this way, the number of elements is, of course, the number of nonzero elements in the array.

Simply put: store the tree in a linear structure, and you can know the length at any time without creating any fantastic algorithm.

Answer 3

The key word for your task is recursion. A tree is a classic recursive structure, so you must write a recursive method that takes root nodes, counts the size of that node, and then calls itself for all the children. Here is the pseudo code:

 public int getSize(ITree root) { return getSize(root, 0); } private int getSize(ITree node, int size) { size++; for(ITree child : node.children()) { size += getSize(child, size) } return size; }