Visitor (pattern) to compute AbstractTree depth

Question

I have such a task at university to write a visitor, which computes the AbstractTree depth. Here is the tree:

public abstract class AbstractTree {
    public abstract void Accept(AbstractVisitor abstractVisitor);
}

public class Leaf : AbstractTree {
    public override void Accept(AbstractVisitor visitor) {
        visitor.VisitLeaf(this);
    }
}

public class Node : AbstractTree {
    private AbstractTree Left { get; set; }
    private AbstractTree Right { get; set; }

    public Node(AbstractTree left, AbstractTree right) {
        Left = left;
        Right = right;
    }

    public override void Accept(AbstractVisitor visitor) {
        visitor.VisitNode(this);

        if (Left != null)
            Left.Accept(visitor);
        if (Right != null)
            Right.Accept(visitor);
    }
}

And AbstractVisitor:

public abstract class AbstractVisitor {
    public abstract void VisitLeaf(Leaf tree);

    public abstract void VisitNode(Node tree);
}

But how do I write the concrete DepthVisitor? I know how to perform this task, when the visitor knows about the tree structure (depth-computing visitor that knows about the tree structure), but in this case, the Visitor has almost no knowledge about the tree structure (it has to, the task is formulated like this).

Answer 1

You could explot some properties of a tree and store the depth of each visited node in the visitor.

• A tree has a single root, so the first node visited has depth 0
• The two children of each node have a depth + 1

Your visitor could keep a map of (tree, depth) pairs.

1. If the current node is unknown it has to be the root. Store (root, 0) and (root.Left, 1), (root.Right, 1).
2. For any other node n, get the depth d of the node from the map (it must be present since the parent node has been visited) and store (n.Left, d+1), (n.Right, d+1)