Abstract tree with visitors

Question

I have very simple abstract class AbstractTree as below:

    public abstract class AbstractTree
    {
        public abstract void Accept(AbstractTreeVisitor visitor);
    }

and two concrete classes: Node with left and right AbstractTree fields and Leaf with integer value (+ overriden method to accept visitors):

public class TreeNode : AbstractTree
{
    public AbstractTree left;
    public AbstractTree right;

    public TreeNode(AbstractTree left, AbstractTree right)
    {
        this.left = left;
        this.right = right;
    }

    public override void Accept(AbstractTreeVisitor visitor)
    {
        visitor.Visit(this);
    }
}

public class TreeLeaf : AbstractTree
{
    public int val;

    public TreeLeaf(int val)
    {
        this.val = val;
    }

    public override void Accept(AbstractTreeVisitor visitor)
    {
        visitor.Visit(this);
    }
}

Now I can write abstract visitor to visiting my tree:

public abstract class AbstractTreeVisitor
{
    public abstract void VisitNode(TreeNode n);
    public abstract void VisitLeaf(TreeLeaf l);

    public virtual void Visit(AbstractTree tree)
    {
        if (tree is TreeNode)
            VisitNode((TreeNode)tree);
        else
            VisitLeaf((TreeLeaf)tree);
    }
}

Thus, lets make concrete visitor which will be computing sum of ints in leafs:

public class SumTreeVisitor : AbstractTreeVisitor
{
    int sum = 0;
    public override void VisitNode(TreeNode n)
    {
        base.Visit(n.left);
        base.Visit(n.right);
    }

    public override void VisitLeaf(TreeLeaf l)
    {
        sum += l.val;
    }

    public int GetSum()
    {
        return sum;
    }
}

Now I can use it in main as:

AbstractTree tree = new TreeNode(new TreeNode(new TreeLeaf(3), new TreeLeaf(4)), new TreeNode(new TreeLeaf(2),new TreeNode(new TreeLeaf(7),new TreeLeaf(3))));
            SumTreeVisitor sum = new SumTreeVisitor();
            tree.Accept(sum);
            int i = sum.GetSum();
            Console.WriteLine(i); //19

But this visitor was really simple.

My question is, how to write Visitor which will find depth of my tree? Of course, in pseudocode it is easy but I have no idea how write it as Visitor. Thanks in advance for help.

Answer 1

First - your AbstractTree should not be a class. It has no data and no behavior. It just defines contract, so it should be declared as interface, e.g.

public interface ITreeNode
{
    void Acept(ITreeVisitor visitor);
}

Also you don't need methods with different names in your visitor class. Signature will be different if parameter types are different. Thus you don't need Visit method and again, you left without data and behavior, pick interface:

public interface ITreeVisitor
{
    void Visit(TreeNode node);
    void Visit(TreeLeaf leaf);
}

Now SumTreeVisitor - you should just accept current visitor on nodes and call will be dispatched to appropriate method of visitor:

public class SumTreeVisitor : ITreeVisitor
{
    public override void Visit(TreeNode node)
    {
        node.Left.Accept(this); // left and right should be properties
        mode.Right.Accept(this);
    }

    public override void Visit(TreeLeaf leaf)
    {
        Sum += leaf.Value;
    }

    public int Sum { get; private set; }
}

Remember to use properties instead of public fields (you can use auto-implemented properties):

public class TreeNode : ITreeNode
{
    public ITreeNode Left { get; private set; }
    public ITreeNode Right { get; private set; }

    public TreeNode(ITreeNode left, ITreeNode right)
    {
        Left = left;
        Right = right;
    }

    public void Accept(ITreeVisitor visitor)
    {
        visitor.Visit(this);
    }
}

And calculating depth is simple - just increment current depth before you visit next node, and decrement it just after you visited it:

public class DepthTreeVisitor : ITreeVisitor
{
    private int _currentDepth = -1;

    public void Visit(TreeNode node)
    {
        _currentDepth++;
        node.Left.Accept(this);
        node.Right.Accept(this);
        _currentDepth--;
    }

    public void Visit(TreeLeaf leaf)
    {
        _currentDepth++;
        if (_currentDepth > Depth)
            Depth = _currentDepth;
        _currentDepth--;
    }

    public int Depth { get; private set; }
}

Passing test:

ITreeNode root = new TreeNode(
new TreeNode(new TreeLeaf(3), new TreeLeaf(4)),
new TreeNode(new TreeLeaf(2),
    new TreeNode(new TreeLeaf(7), new TreeLeaf(3)))
);

var visitor = new DepthTreeVisitor();
root.Accept(visitor);
visitor.Depth.Should().Be(3);