How to determine the depth of a C# Expression Tree Iterativly?

Question

I am 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 under rare (error) conditions, the system can try to process an Expression Tree that is so large that it blows out the stack. I'm trying to figure out a way to check the depth of the tree prior to allowing the tree to be evaluated.

Answer 1

Rather than try to solve your problem for expression trees specifically, let me describe for you some general techniques for dealing with badly-behaved trees.

You might want to start by reading my series of articles on solving the problem you pose: how do I 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

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

Let me give you a little toy example in C# of how to do an operation on a recursive data structure without doing a full recursion. Suppose we have the following binary tree: (Let's assume WOLOG that the binary tree nodes are either zero or two children, never exactly 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 tree p4:

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

and we wish to print out p4 as a parenthesized expression

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

The recursive solution is straightforward:

 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 the tree to be likely "deep" on the left, but "shallow" on the right. Can we eliminate the 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 recurse-on-the-right only version is of course much harder to read and much harder to reason about, but it doesn't blow the stack.

Let's go through 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 output? (((1+2)*3)-(4+5)), as desired.

So you've seen here that I can go from two recursions down to one. We can use similar techniques to go from one recursion down to none. Making this algorithm fully iterative -- so that it recurses neither on the left nor the right -- is left as an exercise.

(And incidentally: I ask a variation of this problem as an interview question, so if you ever get interviewed by me, you now have an unfair advantage!)

Answer 2

The ExpressionVisitor that is included in .Net is recursive, but using a trick, you can turn it into an iterative one.

Basically, you're processing a queue of nodes. For each node in the queue, use base.Visit() to visit all of its children, but then add those children into the queue instead of recursively processing them right away.

This way, you don't have to write code specific to each Expression subtype, but you also work around 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 3

Rather than using recursion to iterate a tree you can always use an explicit in memory structure instead. If you want to closely mimic the recursive behavior you can even use an explicit Stack. Since this is storing all of the information on nodes yet to be processed in the heap, it'll take a heck of a lot more to run out of it.

Here is a general purpose method that traverses a tree based structure (iteratively, not recursively) and returns a flattened sequence of all of the items along with the depth of that item.

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 in the root node(s), a function that maps each element to its direct children, and then we can take the max of the depth. Due to deferred execution each item yielded by the traverse function won't be retained in memory by Max, so the only items held in memory are the nodes who haven't been processed, but have had a parent that has been processed.

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