Traverse a list of tree nodes

Question

I am wondering if there is a better way to traverse a list of trees.

Here is my current algorithm:

1. Collect the parent IDs in a Map
2. Traverse all the groups and find ones where their ID is not in the map
3. Calculate each of those groups overall status, based on their data
4. Go through them again and find their parent
5. Check if the parent has been visited before, if not
6. Find its child groups and its data and calculate an overall status

I have included 6 classes below:

• Main.java ~ Builds the groups, sets the status, and prints the tree(s)
• NodeUtils.java ~ Main library code for traversing the nodes
• Node.java ~ Simple interface that represents a node
• GroupNode.java ~ Represents a group that can hold data and child groups
• DataNode.java ~ Stores a status and other data
• Status.java ~ Represents a status of NORMAL, WARNING, CRITICAL, and UNKNOWN

Here is my current output, which is correct:

A: (WARNING) {0}
    C: (WARNING) {2}
B: (CRITICAL) {1}
    D: (CRITICAL) {1}
    E: (WARNING) {1}
        F: (UNKNOWN) {0}

• The output is group label, status, child count
• Indentation is added for each depth

Main.java

import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<GroupNode> groups = createGroups();

        NodeUtils.calculateStatuses(groups);

        NodeUtils.drawTree(groups);
    }

    private static List<GroupNode> createGroups() {
        GroupNode groupA = new GroupNode(1, "A");
        GroupNode groupB = new GroupNode(2, "B");
        GroupNode groupC = new GroupNode(3, "C");
        GroupNode groupD = new GroupNode(4, "D");
        GroupNode groupE = new GroupNode(5, "E");
        GroupNode groupF = new GroupNode(6, "F");

        DataNode<String> data1 = new DataNode<>(1, "AC1");
        DataNode<String> data2 = new DataNode<>(2, "AC2");
        DataNode<String> data3 = new DataNode<>(3, "BD1");
        DataNode<String> data4 = new DataNode<>(4, "BE1");
        DataNode<String> data5 = new DataNode<>(5, "B1");

        groupC.setParentId(groupA.getId());
        groupD.setParentId(groupB.getId());
        groupE.setParentId(groupB.getId());
        groupF.setParentId(groupE.getId());

        groupC.getChildren().add(data1);
        groupC.getChildren().add(data2);
        groupD.getChildren().add(data3);
        groupE.getChildren().add(data4);
        groupB.getChildren().add(data5);

        data1.setStatus(Status.NORMAL);
        data2.setStatus(Status.WARNING);
        data3.setStatus(Status.CRITICAL);
        data4.setStatus(Status.WARNING);
        data5.setStatus(Status.NORMAL);

        return List.of(groupA, groupB, groupC, groupD, groupE, groupF);
    }
}

NodeUtils.java

import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Optional;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class NodeUtils {
    public static void calculateStatuses(List<GroupNode> groups) {
        Map<Long, Boolean> parentIds = buildParentIdMap(groups);

        for (GroupNode group : groups) {
            if (!parentIds.containsKey(group.getId())) {
                // Does not have any child groups
                group.setStatus(calculateMaxStatus(group.getChildren()));
            }
        }

        for (GroupNode group : groups) {
            if (!parentIds.containsKey(group.getId())) {
                // If unvisited
                if (!parentIds.get(group.getParentId())) {
                    GroupNode parent = findParentGroup(group, groups);
                    List<GroupNode> childGroups = findChildGroups(parent, groups);
                    List<Node> groupsAndData = Stream.concat(childGroups.stream(), parent.getChildren().stream()).collect(Collectors.toList());
                    parent.setStatus(calculateMaxStatus(groupsAndData));
                    parentIds.put(group.getParentId(), true); // Visited
                }
            }
        }
    }

    public static void drawTree(List<GroupNode> groups) {
        List<GroupNode> topLevel = groups.stream().filter(NodeUtils::isRootNode).collect(Collectors.toList());

        topLevel.forEach(node -> visitGroup(node, 0, groups));
    }

    private static void visitGroup(GroupNode group, int depth, List<GroupNode> groups) {
        String indent = "\t".repeat(depth);
        System.out.printf("%s%s: (%s) {%d}%n", indent, group.getLabel(), group.getStatus(), group.getChildren().size());
        findChildGroups(group, groups).forEach(child -> visitGroup(child, depth + 1, groups));
    }

    private static GroupNode findParentGroup(GroupNode group, List<GroupNode> groups) {
        return groups.stream().filter(curr -> curr.getId() == group.getParentId()).findFirst().orElse(null);
    }

    private static List<GroupNode> findChildGroups(GroupNode group, List<GroupNode> groups) {
        return groups.stream().filter(curr -> curr.getParentId() == group.getId()).collect(Collectors.toList());
    }

    private static <E extends Node> Status calculateMaxStatus(List<E> nodes) {
        Status status = Status.UNKNOWN;

        for (E node : nodes) {
            if (node.getStatus().getWeight() < status.getWeight()) {
                status = node.getStatus();
            }
        }

        return status;
    }

    private static boolean invalidId(long id) {
        return id < 1;
    }

    private static boolean isRootNode(GroupNode node) {
        return Optional.of(node).map(GroupNode::getParentId).map(NodeUtils::invalidId).orElse(false);
    }

    private static Map<Long, Boolean> buildParentIdMap(List<GroupNode> groups) {
        Map<Long, Boolean> parentIds = new HashMap<>();

        for (GroupNode group : groups) {
            if (group.getParentId() > 0) {
                parentIds.put(group.getParentId(), false);
            }
        }

        return parentIds;
    }
}

Node.java

public interface Node {
    long getId();

    String getLabel();

    Status getStatus();
}

GroupNode.java

import java.util.ArrayList;
import java.util.List;

public class GroupNode implements Node {
    private long id;
    private long parentId;
    private String label;
    private Status status;
    private List<Node> children;

    public GroupNode(long id, String label) {
        this.id = id;
        this.label = label;
        this.status = Status.UNKNOWN;
        this.children = new ArrayList<>();
    }

    public long getId() {
        return id;
    }

    public void setId(long id) {
        this.id = id;
    }

    public long getParentId() {
        return parentId;
    }

    public void setParentId(long parentId) {
        this.parentId = parentId;
    }

    @Override
    public String getLabel() {
        return label;
    }

    public void setLabel(String label) {
        this.label = label;
    }

    @Override
    public Status getStatus() {
        return status;
    }

    public void setStatus(Status status) {
        this.status = status;
    }

    public List<Node> getChildren() {
        return children;
    }

    public void setChildren(List<Node> children) {
        this.children = children;
    }
}

DataNode.java

public class DataNode<T> implements Node {
    private long id;
    private String label;
    private Status status;
    private T data;

    public DataNode(long id, String label) {
        this.id = id;
        this.label = label;
        this.status = Status.UNKNOWN;
    }

    public long getId() {
        return id;
    }

    public void setId(long id) {
        this.id = id;
    }

    @Override
    public String getLabel() {
        return label;
    }

    public void setLabel(String label) {
        this.label = label;
    }

    @Override
    public Status getStatus() {
        return status;
    }

    public void setStatus(Status status) {
        this.status = status;
    }

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }
}

Status.java

public enum Status {
    NORMAL(100),
    WARNING(10),
    CRITICAL(0),
    UNKNOWN(Integer.MAX_VALUE);

    private int weight;

    Status(int weight) {
        this.weight = weight;
    }

    public int getWeight() {
        return weight;
    }
}

Answer 1

NodeUtils is misrepresented as a static. Convert it to a Tree class with basically all of the same members; most of them will become non-static member functions that refer to a groups member. Once this is a real class, you can add supporting members like an ID index map.

You have too much mutability and too many boilerplate getters+setters (common for Java). In createGroups, there should be no set() calls at all. In fact, given a light refactor of your code, the existing algorithm only needs to mutate one thing, which is your .status. getChildren() should be returning either an unmodifiable list or a stream (which is by its nature unmodifiable).

Many of your List<> arguments can be demoted to Collection<> to be more accepting of multiple collection subclasses.

You have a tendency of flipping between streams and lists a lot. Much of your business logic can stay in the stream domain without intermediate lists.

isRootNode belongs on the node class as a non-static, not in the utils class.

Rather than calling .repeat() on a tab character, consider adding a variable field width in spaces to your format string. Tab formatting is unpredictable.

Your parent ID being "0 for no parent" is not, I think, sufficient distinction from normal integers that do represent parents. Consider a nullable Long instead. invalidId will go away.

calculateMaxStatus is problematic. First, its name is a lie: you're doing a min, not a max. Also, this can be done pretty easily with streams and a lambda comparator.

Node should not be an interface. You have common members and methods so make it an abstract class.

You aren't using the generic data support on DataNode so delete it.

Suggested

Same output as yours.

Main.java

import java.util.List;

public class Main {
    public static void main(String[] args) {
        Tree tree = createTree();
        tree.calculateStatuses();
        tree.draw();
    }

    private static Tree createTree() {
        DataNode data1 = new DataNode(1L, "AC1", Status.NORMAL),
                 data2 = new DataNode(2L, "AC2", Status.WARNING),
                 data3 = new DataNode(3L, "BD1", Status.CRITICAL),
                 data4 = new DataNode(4L, "BE1", Status.WARNING),
                 data5 = new DataNode(5L,  "B1", Status.NORMAL);

        List<GroupNode> groups = List.of(
            new GroupNode(1L, "A"),
            new GroupNode(2L, "B", data5),
            new GroupNode(3L, 1L, "C", data1, data2),
            new GroupNode(4L, 2L, "D", data3),
            new GroupNode(5L, 2L, "E", data4),
            new GroupNode(6L, 5L, "F")
        );

        return new Tree(groups);
    }
}

Node.java

public abstract class Node {
    public final long id;
    public final String label;
    public Status status;

    protected Node(long id, String label) {
        this(id, label, Status.UNKNOWN);
    }

    protected Node(long id, String label, Status status) {
        this.id = id;
        this.label = label;
        this.status = status;
    }
}

DataNode.java

public class DataNode extends Node {
    public DataNode(long id, String label, Status status) {
        super(id, label, status);
    }
}

GroupNode.java

import java.util.Arrays;
import java.util.stream.Stream;

public class GroupNode extends Node {
    public final Long parentId;
    private final Node[] children;

    public GroupNode(long id, String label, Node... children) {
        super(id, label);
        this.parentId = null;
        this.children = children;
    }

    public GroupNode(long id, Long parentId, String label, Node... children) {
        super(id, label);
        this.parentId = parentId;
        this.children = children;
    }

    public Stream<Node> getChildren() {
        return Arrays.stream(children);
    }

    public boolean isRootNode() {
        return parentId == null;
    }

    public int countChildren() {
        return children.length;
    }
}

Status.java

public enum Status {
    NORMAL(100),
    WARNING(10),
    CRITICAL(0),
    UNKNOWN(Integer.MAX_VALUE);

    public final int weight;

    Status(int weight) {
        this.weight = weight;
    }
}

Tree.java

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class Tree {
    private final Collection<GroupNode> groups;
    private final Map<Long, GroupNode> byID;
    private final Map<Long, List<GroupNode>> byParent;


    public Tree(Collection<GroupNode> groups) {
        this.groups = groups;
        this.byID = groups.stream()
            .collect(Collectors.toMap(
                g -> g.id, g -> g
            ));
        this.byParent = groups.stream()
            .filter(g -> g.parentId != null)
            .collect(Collectors.groupingBy(g -> g.parentId));
    }

    public void calculateStatuses() {
        Map<Long, Boolean> parentsVisited = buildParentIdMap();

        for (GroupNode group: groups) {
            if (!parentsVisited.containsKey(group.id)) {
                // Does not have any child groups
                group.status = calculateMinStatus(group.getChildren());
            }
        }

        for (GroupNode group: groups) {
            if (!parentsVisited.containsKey(group.id)) {
                // If unvisited
                if (!parentsVisited.get(group.parentId)) {
                    GroupNode parent = findParentGroup(group);
                    List<GroupNode> childGroups = findChildGroups(parent);
                    Stream<Node> groupsAndData = Stream.concat(childGroups.stream(), parent.getChildren());
                    parent.status = calculateMinStatus(groupsAndData);
                    parentsVisited.put(group.parentId, true); // Visited
                }
            }
        }
    }

    public void draw() {
        groups.stream()
            .filter(GroupNode::isRootNode)
            .forEach(node -> visitGroup(node, 0));
    }

    private void visitGroup(GroupNode group, int depth) {
        System.out.printf(
            "%" + (1 + depth*4) + "s: (%s) {%d}%n",
            group.label, group.status, group.countChildren()
        );
        findChildGroups(group)
            .forEach(child -> visitGroup(child, depth + 1));
    }

    private GroupNode findParentGroup(GroupNode group) {
        return byID.get(group.parentId);
    }

    private List<GroupNode> findChildGroups(GroupNode group) {
        return byParent.getOrDefault(group.id, Collections.emptyList());
    }

    private static Status calculateMinStatus(Stream<Node> nodes) {
        return nodes
            .map(n -> n.status)
            .filter(s -> s != Status.UNKNOWN)
            .min(Comparator.comparing(stat -> stat.weight))
            .orElse(Status.UNKNOWN);
    }

    private Map<Long, Boolean> buildParentIdMap() {
        return byParent.keySet().stream()
            .collect(Collectors.toMap(
                id -> id,            // key
                id -> false,         // value
                (v1, v2) -> false    // merge
            ));
    }
}