Removal of subtrees in tree on condition optimally

Question

I have a small program that removes subtrees of a tree based on following condition: If a subtree consists only of nodes with "rank" 1, remove it. I am using recursive DFS approach. Trees or subtrees does not have any further special properties. I want to ask about your opinions. Is it possible to make this more elegant/more optimal?

public class Main {

    public static void main(String[] args) {
        List<Node> tree1 = Arrays.asList(
            new Node(1, null, 1),
            new Node(2, 1, 1),
            new Node(3, 1, 1),
            new Node(4, 2, 0),
            new Node(5, 3, 1),
            new Node(6, 5, 0),
            new Node(7, 5, 1),
            new Node(8, 7, 0),
            new Node(9, 5, 1),
            new Node(10, 3, 1)
        );

        List<Node> newTree = new ArrayList<>();
        traverse(tree1.get(0), tree1, newTree);
        if(tree1.get(0).rank != 1 || tree1.get(0).getNumberOfValidSubtrees() != 0) {
            newTree.add(tree1.get(0));
        }

        System.out.println(tree1);
        newTree.sort(Comparator.comparing(Node::getId));
        System.out.println(newTree);
    }

    private static void traverse(Node parent, List<Node> allNodes, List<Node> newTree){
        List<Node> children = allNodes.stream().filter(e -> e.parentId != null && e.parentId == parent.id).collect(Collectors.toList());

        for(Node child : children) {
            traverse(child, allNodes, newTree);

            if(child.rank != 1 || child.getNumberOfValidSubtrees() != 0) {
                parent.incrementValidSubtree();
                newTree.add(child);
            }
        }
    }
}

Node class

class Node{
    int id;
    Integer parentId;

    int rank;
    private int numberOfValidSubtrees;

    Node(int id, Integer parentId, int rank){
        this.id = id;
        this.parentId = parentId;
        this.rank = rank;
        this.numberOfValidSubtrees = 0;
    }

    public int getNumberOfValidSubtrees(){
        return this.numberOfValidSubtrees;
    }

    public void incrementValidSubtree() {
        this.numberOfValidSubtrees++;
    }

    public int getId() {
        return id;
    }

    public String toString() {
        return String.valueOf(id);
    }
}

Answer 1

Data Structure

You don't have a Tree of nodes; you have a List of nodes which describes a tree-like structure in a serialized format. This is fine for storing the tree of nodes in a flat database table, but it is not a Tree.

Traversing a Tree can be done in \$O(N)\$ time. Your Depth-First-Search traversal of the List of nodes requires searching the list of nodes repeatedly, once for every node in the list. This makes the algorithm \$O(N^2)\$.

To properly make your tree, you'd need each node to have its own (possibly empty) list of child nodes:

class Node {
    Node parent = null;
    List<Node> children = new ArrayList<>();
}

A depth first search of this tree could then be performed in \$O(N)\$ time.

Code Review

tree1 and newTree don't reflect a consistent naming strategy. tree1 and tree2, or oldTree and newTree would be better.

You use tree1.get(0) four times, to get the root node of the tree. Why not store the root node in a variable?

Node root = tree1.get(0);

Is tree1.get(0) the root node? Always? It looks like you make no assumptions of the order of the nodes in the List<Node> structure. You should probably search for the node with the null parent identifier:

Node root = tree1.stream()
                 .filter(node -> node.parentId == null)
                 .findFirst()
                 .get();

Will the tree always have a root node? If your processing removes all node, and then you call .get(0) on the resulting list, you'll get an IndexOutOfBoundsException.

You repeat this code:

    if(tree1.get(0).rank != 1 || tree1.get(0).getNumberOfValidSubtrees() != 0) {
        newTree.add(tree1.get(0));

here:

        if(child.rank != 1 || child.getNumberOfValidSubtrees() != 0) {
            // ...
            newTree.add(child);

If your traverse() method actually operated on parent instead of the parent's children, you wouldn't need to duplicate code.

Also, if the traverse() method operated on the parent, it could maintain a count of the subtrees, and you wouldn't need to pollute the Node class with numberOfValidSubtrees.

---

Moving on to class Node:

Why is the numberOfValidateSubtrees member private, but none of the other members (id, parentId, rank) are?

Should id and parentId be final? How about rank?

Inconsistent this. usage: You do not need it in getNumberOfValidSubtrees() and in incrementValidSubtree() methods. OR, you should also use it in getId() and toString().

You can remove the this.numberOfValidSubtrees = 0; initialization by providing the initial value in the declaration:

private int numberOfValidSubtrees = 0;

Suggestions

Will it always be rank == 1 nodes with no subtrees that are deleted? A more elegant solution would be to allow a Predicate<Node> argument which would return true if a node was to be deleted.

static boolean isRank1WithNoSubtree(Node node) {
    return node.rank == 1  &&  node.children.isEmpty();
}

static void removeDFS(Predicate<Node> predicate) {
    // ...
}

public static void main(String[] args) {
    // ...
    removeDFS(Main::isRank1WithNoSubtree);
    // ...
}

But there are multiple ways of traversing a tree. Perhaps you would be better with defining methods which traverse the tree, each which take a Consumer<Iterator<Node>> action argument, to call on each tree node as it is visited.

static void removeIfRank1(Iterator<Node> iter) {
    Node node = iter.next();
    if (node.rank == 1  &&  node.children.isEmpty())
        iter.remove();
}

static void traverseDFS(Consumer<Iterator<Node>> action) {
    // ...
}

public static void main(String[] args) {
    // ...
    traverseDFS(Main::removeIfRank1);
    // ...
}

Node -vs- Tree

Personally, I like to draw a distinction between a Node and a Tree. A tree may be a collection of nodes, each node optionally containing more child nodes. But the root node is NOT the tree. The Tree itself can contain additional information about itself, such as the number of nodes it contains. The Tree class would have methods for adding nodes, removing nodes, traversal, filtering, etc., instead of having to tack those methods on to either the Node class or the Main class. Eg):

class Tree<E> {

    class Node<E> {
        Node<E> parent = null;
        List<E> children = new ArrayList<E>();
        E data;

        Node(E e) {
            data = e;
        }
    }

    Node<E> root = null;
    int numNodes = 0;

    void traverseDFS(Consumer<Iterator<Node>> action) {
        // ...
    }
}