Non-Recursive Post Order Depth First Traversal in C#
I was looking around for a non-recursive post-order traversal algorithm and it turned out to be more complex than I thought which surprised me. I mean a recursive post order depth first traversal is so simple.
static void recursivePostOrder(Node node)
{
foreach (var n in node.Children)
{
recursivePostOrder(n);
}
// Do action
Console.WriteLine(node.Id);
}
And a non-recursive Pre Order Depth Traversal isn’t too difficult:
static void preOrder(Node root)
{
Stack<Node> s = new Stack<Node>();
s.Push(root);
while (s.Count > 0)
{
var n = s.Pop();
// Do Action
Console.Write(n.Id);
foreach (var child in n.Children.ToArray().Reverse())
{
s.Push(child);
}
}
}
After doing some searches and consulting some colleagues I couldn’t find a canonical non-recursive post order depth first algorithm (at least one that I could understand quickly). Several of my colleagues also initially thought it was simple and then went back to their offices to later send me alternatives. The essential challenge is to be able to know when the traversal has gone up a level and only at that point doing the “visit” action on the parent node. Here is the most concise alternative I came up with that does not use a full visited list (the full program below):
private static void nonRecursivePostOrder(Node root)
{
var toVisit = new Stack<Node>();
var visitedAncestors = new Stack<Node>();
toVisit.Push(root);
while (toVisit.Count > 0)
{
var node = toVisit.Peek();
if (node.Children.Count > 0)
{
// PeekOrDefault is an extension helper, see full program below
if (visitedAncestors.PeekOrDefault() != node)
{
visitedAncestors.Push(node);
toVisit.PushReverse(node.Children); // PushReverse is a helper, see full program below
continue;
}
visitedAncestors.Pop();
}
Console.Write(node.Id);
toVisit.Pop();
}
}
The idea is here is to, in addition to the normal DFS toVisit stack, keep a visitedAncestors stack. In the depth first traversal when we encounter a parent node (node.Children.Count > 0), if it hasn’t been visited yet (visitedAncestors.PeekOrDefault() != node), then add the children to the stack and don’t process the parent yet (leave the parent on the toVisit stack). The next time the parent node is hit, the children will have already been processed then remove it from the visitedAncestors stack (visitedAncestors.Pop()) and drop down to process the parent node.
There are multiple algorithms out there to accomplish this. Several of my colleagues sent me their versions. One version kept the state of child enumeration in the stack along with the node in the toVisit stack. Another similarly used a structure in the toVisit stack that had a visited boolean along with the node. This one also used an interesting linked list approach to the toVisit stack that allowed the children to not have to be reversed (if the childlist is forward only as it is in many trees then it has to be materialized in order to reverse it). Still another colleague offered an algorithm in which the toVisit stack contains a boolean that keeps track of direction (down/child or next/sibling) and makes the action decision accordingly. If there is interest I can likely publish these algorigthms as well. What I am not sure of is whether there is a canonical “best” (complexity, space) algorithm for a non-recursive post order traversal.
Here is a full sample program with the helper methods and sample tree data structure:
using System;
using System.Collections.Generic;
using System.Linq;
namespace ConsoleApplication2
{
class Program
{
static void Main(string[] args)
{
// a
// b c d
// e f g h i
// dfs: efbgchida
var root = makeTree();
nonRecursivePostOrder(root);
Console.WriteLine();
}
private static void nonRecursivePostOrder(Node root)
{
var toVisit = new Stack<Node>();
var visitedAncestors = new Stack<Node>();
toVisit.Push(root);
while (toVisit.Count > 0)
{
var node = toVisit.Peek();
if (node.Children.Count > 0)
{
if (visitedAncestors.PeekOrDefault() != node)
{
visitedAncestors.Push(node);
toVisit.PushReverse(node.Children);
continue;
}
visitedAncestors.Pop();
}
Console.Write(node.Id);
toVisit.Pop();
}
}
private static Node makeTree()
{
var e = new Node("e");
var f = new Node("f");
var b = new Node("b", new List<Node> { e, f });
var g = new Node("g");
var c = new Node("c", new List<Node> { g });
var h = new Node("h");
var i = new Node("i");
var d = new Node("d", new List<Node> { h, i });
var a = new Node("a", new List<Node> { b, c, d });
return a;
}
}
static class StackHelper
{
public static Node PeekOrDefault(this Stack<Node> s)
{
return s.Count == 0 ? null : s.Peek();
}
public static void PushReverse(this Stack<Node> s, List<Node> list)
{
foreach (var l in list.ToArray().Reverse())
{
s.Push(l);
}
}
}
class Node
{
public string Id;
public List<Node> Children;
public Node(string id)
{
Id = id;
Children = new List<Node>();
}
public Node(string id, List<Node> children)
{
Id = id;
Children = children;
}
public override bool Equals(object obj)
{
var node = obj as Node;
if (node != null)
{
return node.Id == this.Id;
}
return false;
}
public override int GetHashCode()
{
return Id.GetHashCode();
}
}
}