Recursively creating a mathematical expression binary tree

Question

Afternoon all,

I have implemented a simple binary tree in C#, I intend on using it to create mathematical expression trees recursively. But I am running into problems, as it has been years since I have had to do recursive calls I am struggling to get my heard around why the following only works for binary trees of depth 2 and not trees of any greater depth.

Surely if the recursion was correct it should be able to construct trees to depth n. Here is the code :

Node<T> f;
Node<T> t;
Node<T> subRoot;
Node<T> root;

////Only works with trees of depth 2.

private Node<T> Tree(List<T> prefixBank, int maxDepth)
{
    if (prefixBank.Count != 0)
    {
        if (maxDepth == 0)
        {
            t = new Node<T>(prefixBank[0]);
            subRoot.Add(t);

            prefixBank.Remove(prefixBank[0]);
        }
        else
        {
            if (root == null)
            {
                root = new Node<T>(prefixBank[0]);
                prefixBank.Remove(prefixBank[0]);
                Tree(prefixBank, maxDepth - 1);
            }

            f = new Node<T>(prefixBank[0]);

            if (isOperator(f))
            {
                root.Add(f);
                prefixBank.Remove(prefixBank[0]);
                subRoot = f;
            }

            for (int i = 0; i < 2; i++)
            {
                Tree(prefixBank, maxDepth - 1);
            }
        }
    }
return f;
}

The above function takes a list of characters that form a prefix mathematical expression (for example * + 3 4 - 5 6). Annoyingly I create the prefix expression recursively using this code:

string prefixExpression = String.Empty;

private string generateExpression(Random rand, GenerationMethod generationMethod, int maxDepth)
{
    if ((maxDepth == 0) || ((generationMethod == GenerationMethod.Grow) && (rand.NextDouble() < randomRate)))
    {
        operand.GenerateValue(Type.Terminal, rand);
        prefixExpression += " " + operand.Value;
    }
    else
    {
        operator.GenerateValue(Type.Function, rand);
        prefixExpression += " " + operator.GeneValue;

        //2 is the arity of the function right an arity checker function so that unary operators can be utilised
        for (int i = 0; i < 2; i++)
        {
            generateExpression(rand, generationMethod, maxDepth - 1);
        };
    }
    return prefixExpression;
}

I have tried to create a tree in the same way I have generated the string but cannot get it to work in any common sense way. I am using a slightly modified version of the binary tree class found on MSDN. I modified it to have an add function that automatically added to either the left or right subtree so I dont have to specify Root.Left.Left.Left etc like this example does to create the tree.

If any body could help me correct my recursive tree creation code so that it works for trees of n depth I would really appreciate it. Im relatively new to C# so I apologise if anything above is slightly sketchy.

Not relevant to your question, but instead of concatenating strings the way you do, you should use StringBuilder. — svick
– svick, Commented Mar 27, 2011 at 13:55

svick · Accepted Answer · 2011-03-27 17:23:26Z

2

You shoudn't rely on global variables when making recursive calls like this (and in general, the scope of your variables should be as narrow as possible, there doesn't seem to be any reason for f and t to be class-level variables). Your code doesn't make much sense to me, but I guess the main probelm is that you are adding every node directly to the root. I would do it like this:

public Node<T> Tree(Queue<T> prefixBank)
{
    var node = new Node<T>(prefixBank.Dequeue());

    if (isOperator(node))
    {
        for (int i = 0; i < 2; i++)
        {
            node.Add(Tree(prefixBank));
        }
    }

    return node;
}

I don't see much reason to have maxDepth there, but if you really want it, it should be trivial to implement.

Also, it might make sense to have a inheritance hierarchy of nodes (like NumberNode, OperatorNode), but that depends on what exactly do you want to do with them.

EDIT: @Eric, not much. I can use IEnumerator<T> instead of Queue<T> (which, now that I think about it, is probably a better choice anyway). And I have to pospone the creation of the result until the end, wchich also means I have to modify isOperator() to work on T and not Node<T>.

public Node<T> Tree(IEnumerable<T> prefixBank)
{
    return Tree(prefixBank.GetEnumerator());
}

public Node<T> Tree(IEnumerator<T> enumerator)
{
    enumerator.MoveNext();
    var value = enumerator.Current;

    var children = new List<Node<T>>(2);

    if (isOperator(value))
    {
        for (int i = 0; i < 2; i++)
        {
            children.Add(Tree(enumerator));
        }
    }

    return new Node<T>(value, children);
}

edited Mar 27, 2011 at 17:23

answered Mar 27, 2011 at 14:27

svick

247k54 gold badges407 silver badges536 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Eric Lippert Over a year ago

A challenge, should you have some spare time: suppose that (1) you did not wish to destroy the input object by dequeing it, and (2) the nodes were immutable. How might you modify your algorithm?

user648132 Over a year ago

This worked a treat. Learnt a valuable lesson here, thanks @svick.

user648132 Over a year ago

in your opinion would it be better to generate and add the nodes to the tree at the same time. As opposed to having the intermediary stage of storing them in the queue. A I right in assuming that this can be done recursively as well ???

svick Over a year ago

Yeah, I think it would be better to do it without the additional step.

Node<T> generate(int level) { return level == 0 ? new Node<T>(generateOperand(), new Node<T>[0]) : new Node<T>(generateOperator(), new[] { generate(level-1), generate(level-1) }; }

Collectives™ on Stack Overflow

Recursively creating a mathematical expression binary tree

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related