Search code examples
c#treenodestraversalinorder

What traversal will produce the output I need

I have a tree of nodes in this form:

enter image description here

I need to be able to traverse the tree in order to produce the output:

a / b + c

The nodes labelled 'node' are for structure and I know which nodes are the ones which contain the correct values so the output can be:

a node / b node node + node c node

as when the excess nodes are removed the output will still be:

a / b + c

I think I need to implement a InOrder traversal but I'm struggling to get anything to properly work.

edit:

public IEnumerable<Node> PostOrder(Node start, Func<Node, IEnumerable<Node>> getNeighbours)
{
    HashSet<Node> visited = new HashSet<Node>();
    Stack<Node> stack = new Stack<Node>();
    stack.Push(start);

    while (stack.Count != 0)
    {
        Node current = stack.Pop();
        visited.Add(current);
        yield return current;

        IEnumerable<Node> neighbours = getNeighbours(current).Where(node => !visited.Contains(node));

        foreach (Node neighbour in neighbours)
        {
            stack.Push(neighbour);
        }
    }
}

However this returns the list:

Root, node, c, node, +, node, node, b, node, /, node, a

(goes from left to right)

Solution

  • I was being stupid...

    I just need to reverse the output.

    Just one of those days -_-