How to traverse a Tree in Depth First Order using Stacks without Recursion (in Java)

249

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]

1 COMMENT

LEAVE A REPLY

Please enter your comment!
Please enter your name here