Consider a tree structure made up of Nodes and their specialized subclasses. Each Node has children which could be subclasses of Node.
We’re going to traverse this tree structure without using recursion but only using 2 Stacks.
Here goes the code:
[box_dark]
/**
* Returns a {@link Stack} having a Tree ordered in Depth First whose root is passed as the Parameter
*
* @param <T> The implementation of {@link Node}
* @param treeRoot The root of the tree
* @return The {@link Stack} of T
*/
public static <T extends Node> Stack<T> depthFirstOrder(final T treeRoot)
{
// Main stack, where the important stuff go
Stack<T> mainStack = new Stack<T>();
// Temp child stack, where we store children of before it gets put to the mainStack
Stack<Node> tempChildStack = new Stack<Node>();
mainStack.push(treeRoot); // Put the tree root
tempChildStack.addAll(treeRoot.getChildren()); // Put the children to the temp
// Loop until no more children in the temp stack
while (!tempChildStack.isEmpty())
{
T node = (T) tempChildStack.pop(); // Keep popping from the temp stack..
mainStack.push(node); // .. and Push to the main stack..
tempChildStack.addAll(node.getChildren()); // .. while adding children to temp
}
// Now temp stack is empty and mainStack has things in DFS order!
return mainStack;
}
[/box_dark]
Thank you , it explained it very well 🙂