How to determine the depth of a C # Iterativly expression tree?

Question

I'm trying to figure out if there is a good way to figure out the depth of a particular C # expression tree using an iterative approach. We use expressions for some dynamic evaluation and in rare (errors) conditions, the system may try to process the Expression Tree, which is so large that it removes the stack. I am trying to figure out a way to check the depth of a tree before allowing the tree to be evaluated.

Answer 1

ExpressionVisitor , which is included in .Net, is recursive, but with a trick you can turn it into iterative.

Basically, you process the node queue. For each node in the queue, use base.Visit() to view all of its children, and then add these children to the queue, rather than recursively process them immediately.

Thus, you do not need to write code specific to each Expression subtype, but you also work with the recursive nature of ExpressionVisitor .

 class DepthVisitor : ExpressionVisitor { private readonly Queue<Tuple<Expression, int>> m_queue = new Queue<Tuple<Expression, int>>(); private bool m_canRecurse; private int m_depth; public int MeasureDepth(Expression expression) { m_queue.Enqueue(Tuple.Create(expression, 1)); int maxDepth = 0; while (m_queue.Count > 0) { var tuple = m_queue.Dequeue(); m_depth = tuple.Item2; if (m_depth > maxDepth) maxDepth = m_depth; m_canRecurse = true; Visit(tuple.Item1); } return maxDepth; } public override Expression Visit(Expression node) { if (m_canRecurse) { m_canRecurse = false; base.Visit(node); } else m_queue.Enqueue(Tuple.Create(node, m_depth + 1)); return node; } } 

Answer 2

Instead of trying to solve your problem specifically for expression trees, let me describe for you some general methods for working with poorly managed trees.

You can start by reading my series of articles on solving your problem: how to determine the depth of a tree without using recursion?

http://blogs.msdn.com/b/ericlippert/archive/2005/07/27/recursion-part-one-recursive-data-structures-and-functions.aspx

These articles were written when I was working on JScript, so the examples are in JScript. It's not too hard to understand how to apply these concepts to C #.

Let me give you a small example of a toy in C # on how to do an operation on a recursive data structure without doing a full recursion. Suppose we have the following binary tree: (Assume WOLOG that binary tree nodes have either zero or two children, not one).

 class Node { public Node Left { get; private set; } public Node Right { get; private set; } public string Value { get; private set; } public Node(string value) : this(null, null, value) {} public Node(Node left, Node right, string value) { this.Left = left; this.Right = right; this.Value = value; } } ... Node n1 = new Node("1"); Node n2 = new Node("2"); Node n3 = new Node("3"); Node n3 = new Node("4"); Node n5 = new Node("5"); Node p1 = new Node(n1, n2, "+"); Node p2 = new Node(p1, n3, "*"); Node p3 = new Node(n4, n5, "+"); Node p4 = new Node(p2, p3, "-"); 

So we have the p4 tree:

  - / \ * + / \ / \ + 3 4 5 / \ 1 2 

and we want to print p4 as an expression in brackets

  (((1+2)*3)-(4+5)) 

The recursive solution is simple:

  static void RecursiveToString(Node node, StringBuilder sb) { // Again, assuming either zero or two children. if (node.Left != null) sb.Append(node.Value); else { sb.Append("("); RecursiveToString(node.Left, sb); sb.Append(node.Value); RecursiveToString(node.Right, sb); sb.Append(")"); } } 

Now suppose we know that the tree is probably “deep” on the left, but “shallow” on the right. Is it possible to exclude recursion on the left?

  static void RightRecursiveToString(Node node, StringBuilder sb) { // Again, assuming either zero or two children. var stack = new Stack<Node>(); stack.Push(node); while(stack.Peek().Left != null) { sb.Append("("); stack.Push(stack.Peek().Left); } while(stack.Count != 0) { Node current = stack.Pop(); sb.Append(current.Value); if (current.Right != null) RightRecursiveToString(current.Right, sb); sb.Append(")"); } } } 

The review of the right only the version, of course, is much more difficult to read and much more difficult to reason, but it does not hit the glass.

Let's move on to our example.

 push p4 push p2 output ( push p1 output ( push n1 output ( loop condition is met pop n1 output 1 go back to the top of the loop pop p1 output + recurse on n2 -- this outputs 2 output ) go back to the top of the loop pop p2 output * recurse on n3 -- this outputs 3 output ) go back to the top of the loop pop p4 output - recurse on p3 push p3 push n4 output ( loop condition is met pop n4 output 4 go back to the top of the loop pop p3 output + recurse on n5 -- this outputs 5 output ) loop condition is not met; return. output ) loop condition is not met, return. 

And what do we infer? (((1+2)*3)-(4+5)) if required.

So, you saw here that I can go from two recursions to one. We can use similar methods to go from one recursion to one. To make this algorithm completely iterative - so that it does not repeat either on the left or on the right - is left as an exercise.

(And by the way: I ask a variant of this problem as an interview question, so if you ever intend to interview me, you now have an unfair advantage!)

Answer 3

Instead of using recursion to iterate through the tree, you can always use the explicit in the memory structure. If you want to accurately simulate recursive behavior, you can even use explicit Stack . Since this stores all the information about the nodes that have yet to be processed on the heap, more will be needed to exhaust it.

Here is a general method that bypasses the tree structure (iteratively, not recursively) and returns a flattened sequence of all elements along with the depth of that element.

 public static IEnumerable<Tuple<T, int>> TraverseWithDepth<T>(IEnumerable<T> items , Func<T, IEnumerable<T>> childSelector) { var stack = new Stack<Tuple<T, int>>( items.Select(item => Tuple.Create(item, 0))); while (stack.Any()) { var next = stack.Pop(); yield return next; foreach (var child in childSelector(next.Item1)) { stack.Push(Tuple.Create(child, next.Item2 + 1)); } } } 

Now, to use this, all we need to do is pass to the root directory node (s), a function that displays each element in its direct children, and then we can take the maximum depth. Due to delayed execution, each element received by the traverse function is not stored in Max memory, therefore the only items stored in memory are nodes that were not processed, but they had a parent that was processed.

 public static int GetDepth(Expression t) { return TraverseWithDepth(new[] { t }, GetDirectChildren) .Max(pair => pair.Item2); }