How to track depth in this search algorithm by object depth?

Question

I have this code that iterates over a tree, doing a deep search. Each element is solved exactly once. Very good.

-(void)iterateOverTree:(TreeNode *)node { NSMutableArray * elements = [NSMutableArray array]; [elements addObject:node]; while([elements count]) { TreeNode * current = [elements objectAtIndex:0]; [self doStuffWithNode:current]; for(TreeNode * child in current.children) { [elements addObject:child]; } [elements removeLastObject]; } } 

BUT: How can I track the current depth on the chart? I need to know the level of depth. So, for example, I have these nodes:

A has children B, J. B has a child C. C has a child D. D has children E, F, I.

When A is at depth level 1, then B is 2 and C is 3.

With recursion, it was very easy to track the current depth level. Just process the variable before calling yourself and reduce it after calling yourself.

But here with this fantasy cycle, which is impossible. There is no window in the box in the box, as with recursion.

I really do not want to add properties (or instance variables) to the TreeNode object, as this should be reused in a universal way for any type of object graph.

Does anyone have an idea how to do this? Should I introduce another array to track visited sites?

Answer 1

I think you also need to collect the depth. This is what you would actually do if you had a recursive version. It is just that the repository will be “invisible”, since you would use the call stack instead of the explicit stack, as you are doing now.

If this helps you, you can easily convert a depth search to a width search, using the array as a queue instead of a stack. (Just remove FirstObject instead of removeLastObject.) Then you should know that you always look at nodes in order of non-decreasing depth. However, if you need accurate depths, I think you still need to add storage to keep track of when you need to increase your current depth.

Update:

You should be able to do DFS without a stack at all, if instead you follow the parent's pointers from node to back up the tree. This would make maintaining depth easier. But you have to be careful not to disturb the complexity of the worst case with linear time, retelling the children to find out where you were.

If you do not have parent pointers, you should be able to collect enough information to track your parents. But that would mean that you are adding more information about the stack than you are currently doing, so this will not be a big improvement over laying the depths directly.

By the way, looking carefully at your algorithm, don't you look at the wrong side of the array when you get the next current node? It should work as follows:

 push root while stack not empty: current = pop push all children of current 

Answer 2

I don’t understand your notations, but if I read it correctly, you will process the node and add all the children to the list of your work.

If you can change this part to use recursion, you can track the depth of the tree, as this will be the depth of the recursion.

So, instead of adding a node child, recurse for each node child.

Hth

Mario

Answer 3

I believe that you are actually doing BFS. You work with lists. You must use the stack to run DFS;

This can be useful for the depth track, you can look at the vector p (of the parents)

Answer 4

Assuming you are doing BFS, the easiest way is to enter another queue for depth that reflects the queue of your nodes. Initialize the depth to zero. Each time you click on the node queue, click the current depth + 1 in the depth queue.