I have the following recursive method.It evaluates a node (that represent a logical expression), using deep first search traversal :EvaluateNode(Node node){    bool result;    switch(node.Type)    {        case AND_OPERATOR:            result = true;            foreach(Node nodeChild in node.Childrens)            {                childresult = EvaluateNode(nodeChild);                result = result && childresult;            }        case OR_OPERATOR:            result = false;                            foreach(Node nodeChild in node.Childrens)            {                childresult = EvaluateNode(nodeChild);                result = result || childresult;            }        case VALUE:            result = node.Value;    }    return result;}I'd like to convert this to a stack/queue based, non recursive solution. Here is what I tried so far (incomplete) :bool result;stack.Push(node);while(!stack.Empty()){    Node node = stack.Pop();    switch(node.Type)    {        case AND_OPERATOR:            foreach(Node nodeChild in node.Childrens)            {                stack.Push(nodeChild);            }           case OR_OPERATOR:            foreach(Node nodeChild in node.Childrens)            {                stack.Push(nodeChild);            }                   case VALUE:            result = node.Value;    }}My guess is that I would need another stack for storing results but I have not been able to figure this out.
How to convert the following node evaluation procedure to a non recursive solution?
c#;algorithms;recursion;stack;evaluation
You are doing a Breadth-first search. There is typicall two way to approach this: recursive and non-recursive.You can find a pseudo code for a non-recursive algorithm here:http://en.wikipedia.org/wiki/Breadth-first_search#AlgorithmYou will of course need to tailor it for your own needs, but it does not really change the principal.UPDATEBen Aaronson is right (comment bellow). This is not Breadth-first. It is Depth-first:http://en.wikipedia.org/wiki/Depth-first_search#PseudocodeSorry for the confusion.UPDATE 2I think this also doesn't really address OP's problem, which is that what to do with each node depends on its parent, so you can't just push the individual nodes to the stack Ben AaronsonI disagree. The tree traversal and the evaluation can be seperated from each other. Here is how you do it:IEnumerable<Node> PostOrderDFS(Node root){  ...}Note that in post order DFS the children directly precedes the parent. A possible implementation is here:http://blogs.msdn.com/b/daveremy/archive/2010/03/16/non-recursive-post-order-depth-first-traversal.aspxThe only thing you need to change here is the return type, and make a yield return instead of Console.Write.The evaluation would look like this:bool Evaluate(Node root){  List<Tuple<Node, bool>> traverseList = PostOrderDFS(root).Select(n => Tuple.Create(n, false)).ToList();  for(int i = 0; i < traverseList.Count; ++i)  {    Tuple<Node, bool> tuple = traverseList[i];    Node node = tuple.Item1;    switch(node.Type)    {    case AND_OPERATOR:        tuple.Item2 = true;        foreach(int j = 1; j <= node.Childrens.Count; ++j)        {            bool childresult = traverseList[i-j].Item2;            tuple.Item2 = tuple.Item2 && childresult;        }    case OR_OPERATOR:        tuple.Item2 = false;        foreach(int j = 1; j <= node.Childrens.Count; ++j)        {            bool childresult = traverseList[i-j].Item2;            tuple.Item2 = tuple.Item2 || childresult;        }    case VALUE:        tuple.Item2 = node.Value;    }  }  return traverseList.Last().Item2;}