2
\$\begingroup\$

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);
    }
}
\$\endgroup\$
2
\$\begingroup\$

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) {
        // ...
    }
}
\$\endgroup\$
  • \$\begingroup\$ Encapsulating a node in a tree seems an avoidable increase in complexity to me. Each node is a tree imo. The manipulation and search methods should be part of the node. \$\endgroup\$ – dfhwze May 27 at 6:12
  • \$\begingroup\$ @dfhwze If a node is a tree, you can’t have two or more references to the same empty tree. With the Tree class, an empty tree is still a container object, which you can have multiple references to. Adding public manipulation and search methods to Node seems “vulgar”; adding these methods to the container seems more “elegant”. (Of course, you can add as many private helper search/manipulation methods to Node as you deem useful.) \$\endgroup\$ – AJNeufeld May 27 at 15:56
  • 1
    \$\begingroup\$ Most public API's that allow containers with nodes (WPF Components, WinForms Components, XML Document, ..) ensure the best of both worlds. The Container would be a derived class of Node and the manipulation methods would be on the Container class. \$\endgroup\$ – dfhwze May 27 at 16:01
  • 1
    \$\begingroup\$ after some debate, I do agree with your wrapper for scenarios where the root itself could be interchanged with another. \$\endgroup\$ – dfhwze May 27 at 16:27
  • 1
    \$\begingroup\$ And I concede: while “a tree is-a node” is not always true, in the problem domains where it is true, it can be a useful optimization. \$\endgroup\$ – AJNeufeld May 27 at 16:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.