CODEWITHSUNDEEP
javatreetraversalpostorder
jabronski
jabronski

Reputation: 13

How can I do a post-order traversal of a tree, when the only function I have is getChildren()?

I'm trying to collect all nodes in specific post-order traversal order. However, I'm not quite sure how to do this when my only function is getChildren(), rather than a left or right child. Here is the traversal I currently have, in Java.

Set<Node> postOrderedNodes = traverseSubAssembly(rootNode);

private static Set<Node> traverseSubAssembly(Node node) {

        Set<Node> nodes = new LinkedHashSet<>();

        nodes.add(node);

        for (Node child : node.getChildren()) {
            nodes.addAll(traverseSubAssembly(child));
        }

        return nodes;
    }

Upvotes: 0

Views: 61

Answers (1)

Naren D
Naren D

Reputation: 126

Set<Node> postOrderedNodes = traverseSubAssembly(rootNode);

private static Set<Node> traverseSubAssembly(Node node) {
    Set<Node> nodes = new HashSet<>();

    for (Node child : node.getChildren()) {
        nodes.addAll(traverseSubAssembly(child));
    }

    nodes.add(node);  
    // Add the node after its children have been processed not before.

    return nodes;
}

To get exact Order:

And also one more thing if you need to maintain insertion order of nodes U can use LinkedHashSet since hashSet does not maintain.

Upvotes: 1

Related Questions