How to evaluate expression tree with logical operators in C#

Question

I have a tree structure with leaf nodes containing expressions, which are asserted to be True or False , connected by Logical (AND/OR) conditions. I am looking for an algorithm/solution to evaluate the tree by Depth-first-search, based on logical-operators If the parent node is an AND then no further traversal to sibling is required if the current node is evaluated as false. (also if the current node is TRUE then no further sibling to be visited if the parent node is an OR) - This would optimize the evaluation.I am just curious to know if there is a solution/code already there, rather than reinventing it.

public class TreeNode<T>
{
    private readonly T _value;
    private readonly List<TreeNode<T>> _children = new List<TreeNode<T>>();

    public TreeNode(T value)
    {
        _value = value;
    }

    public TreeNode<T> this[int i]
    {
        get { return _children[i]; }
    }

    public TreeNode<T> Parent { get; private set; }

    public T Value { get { return _value; } }

    public ReadOnlyCollection<TreeNode<T>> Children
    {
        get { return _children.AsReadOnly(); }
    }

    public TreeNode<T> AddChild(T value)
    {
        var node = new TreeNode<T>(value) {Parent = this};
        _children.Add(node);
        return node;
    }

    public TreeNode<T>[] AddChildren(params T[] values)
    {
        return values.Select(AddChild).ToArray();
    }

    public bool RemoveChild(TreeNode<T> node)
    {
        return _children.Remove(node);
    }

    public void Traverse(Action<T> action)
    {
        action(Value);
        foreach (var child in _children)
            child.Traverse(action);
    }

    public IEnumerable<T> Flatten()
    {
        return new[] {Value}.Union(_children.SelectMany(x => x.Flatten()));
    }
}

Note: I could easily do a recursive BFS in C#, But found this one tougher Image of sample tree structure

Answer 1

Do a recursive traversal of the tree. You collect the result of evaluating each child node, then apply your logical operation and return the result. The basic logic would be like below.

The code is a C#-like pseudocode. It's not clear to me from the code you posted how you differentiate between operator nodes (AND and OR) from nodes that have values True and False. But you should be able to use this basic algorithm with a few changes to fit your code.

bool EvaluateNode(TreeNode node)
{
    // if it's a child node, return its value
    if (node has no children)
    {
        return node._value;
    }

    switch node.Operator
    {
        case operator.AND:
            // for AND, we can shortcut the evaluation if any child
            // returns false.
            for each child
            {
                if (EvaluateNode(child) == false)
                    return false;
            }
            // all children returned true, so it's true
            return true;

        case operator.OR:
            // for OR, we can shortcut the evaluation if any child
            // returns true.
            for each child
            {
                if (EvaluateNode(child) == true)
                    return true;
            }
            // none were true, so must be false
            return false;
        default:
            // Unknown operator. Some error.
            break;
    }

}

If you don't want to do shortcut evaluation, this still works. You just change your loops slightly. For example, the AND case would be:

bool result = true;
for each child
{
    result = result & EvaluateNode(child);
}
return result;

And the OR case would be:

bool result = false;
for each child
{
    result = result | EvaluateNode(child);
}
return result;