CODEWITHSUNDEEP
javaalgorithmdata-structurestreetraversal
mhshams
mhshams

Reputation: 16972

Traverse a Tree - But Step by Step

I have following code to traverse a tree (pre-order): 

public void traverse(Node node) {
    visit(node);
    for (Node child : node.getChildren()) {
        traverse(child);
    } 
}

I would like have a step-by-step traverse. something like an Iterator, so that a client ( caller ) who can be another application, can have control over traverse. (for example: in UI we have a "Next" button and by clicking on this button, we have to visit next node)

my current solution is something like this: 

List<Node> nodes = new ArrayList<Node>();
collectNodes(root, nodes);
Iterator<Node> it = nodes.iterator();
// do my job.
...

public void collectNodes(Node node, List<Node> nodes) {
    nodes.add(node);
    for (Node child : node.getChildren()) {
        collectNodes(child, nodes);
    } 
}

As you can see in the code, I'm visiting all nodes ( in collectNodes) to collect and put them in a List in pre-order format.

I was wondering if there is any solution without this extra (collectNodes) iteration ?

Regards, Mohammad

Upvotes: 3

Views: 4352

Answers (3)

Tapan
Tapan

Reputation: 1

Don't you think the last line if your code collectNodes(child) would give an error since the collectNodes() method will accept two arguments.

Upvotes: 0

LiKao
LiKao

Reputation: 10658

The idea behind the algorithm you posted is to use the method stack as an implicit data structure. Whenever you enter traverse all nodes are implicitly pushed onto the function stack, and when you then iterate over them they are popped.

Now to make this algorithm suspendable like an iterator, all you need to do is to make this implicit stack explicit. Add a stack to your class, on visiting push all children, and then always use the top-node on the stack to continue. You can suspend this at any time, while you keep the stack as a state that you can suspend and store anywhere.

This trick actually works for any kind of recursive algorithm.

Upvotes: 3

Bhavik Ambani
Bhavik Ambani

Reputation: 6657

You can find the code for traversal of the tree using iterator step by step here

Hope this will help you.

Upvotes: -1

Related Questions