Finding the weight of the heaviest path in a binary tree

Question

I'm fairly new to Java, arriving in the "future" from C and returning to type safety from Python. I've programmed an algorithm to return the weight of the heaviest path from the root of a binary tree to one of its leaves.

Each Node in the tree has a weight (its data). The weight of the path is the sum of all of the Nodes weights from root to leave inclusive. This algorithm finds the heaviest.

I'm looking for your suggestions to improve this code in the following areas:

1. Terminology - is there a name for this problem? have I used conventional names for things?
2. Correctness - are there any bugs?
3. Java conventions and idioms - can I make better use of the standard libraries?
4. Runtime performance.
5. Repetition - is there any way to avoid writing the field names 4 times each?

package binaryTree;

class Node {
    Integer data;
    Node left;
    Node right;

    public Node(Integer data, Node left, Node right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }

    public Node(Integer data) {
        this(data, null, null);
    }

}

public class BinaryTree {

    /**
     * Finds the heaviest path in the tree from the given @root Node to a leaf Node.
     * @param root
     * @return integer representing the sum weight of the heaviest path.
     */
    public static int getHeaviestPathWeight(Node root) {
        if (root == null)
            return 0;
        else
            return root.data + Math.max(getHeaviestPathWeight(root.left), getHeaviestPathWeight(root.right));
    }

}

Answer 1

The algorithm looks sound. It visits every node once, and cannot be more efficient than that.

I find it odd that you split the code into two classes, one of which is non-public. Since the Node class is non-public, no code in any other package will be able to construct a Node. The algorithm is therefore "unusable".

There are two ways to model a tree: a "lazy" way (exposing the nodes, and a tree is just referred to by its root node) and a "polished" way (with the tree being an opaque data structure that hides and manages its nodes). Here, you have an odd hybrid.

If you want to have a BinaryTree class that contains nothing but a static method, then you should suppress the implicit no-argument default BinaryTree() constructor by making it private:

public class BinaryTree {
    // Suppress the default constructor
    private BinaryTree() {}

    public static int getHeaviestPathWeight(…) {
        …
    }
}

Package names are conventionally all lowercase.

Whenever possible, use int instead of Integer. Using Integer objects is less efficient and usually results in more complicated source code and bytecode. One reason why you might need an Integer instead of an int would be to store a null — and that sounds more like a liability than an advantage in this case.

To language purists, "data" is plural, and "datum" is singular. However, I would suggest a different name altogether, such as weight.

Simple solution

package binarytree;

public class BinaryTree {
    private final int weight;
    private final BinaryTree left, right;

    public BinaryTree(int weight, BinaryTree left, BinaryTree right) {
        this.weight = weight;
        this.left = left;
        this.right = right;
    }

    public BinaryTree(int weight) {
        this(weight, null, null);
    }

    /**
     * JavaDoc here
     */
    public int getHeaviestPathWeight() {
        return this.weight + Math.max(
            this.left  == null ? 0 : this.left.getHeaviestPathWeight(),
            this.right == null ? 0 : this.right.getHeaviestPathWeight()
        );
    }
}

Alternate solution

package binarytree;

public class Node {
    public final int datum;
    public final Node left, right;

    public Node(int datum, Node left, Node right) {
        this.datum = datum;
        this.left = left;
        this.right = right;
    }

    public Node(int datum) {
        this(datum, null, null);
    }
}

---

public class HeaviestPath {
    private HeaviestPath() {}

    /**
     * JavaDoc here
     */
    public static int weight(Node root) {
        if (root == null) {
            return 0;
        } else {
            return root.datum + Math.max(weight(root.left), weight(root.right));
        }
    }
}

Answer 2

It looks quite good.

A very small detail is that I would make the Node class immutable, which just means that you have to add private final qualifiers to the declarations of data, left and right. It has no impact on your current code, but it could restrict what you can do if you expand your class since you cannot modify a Node.

Immutability is a concept that comes mainly from functional programming, but it is creeping in all languages. Immutability is useful because it greatly simplifies reasoning about programs. If your classes are mutable, you have to be aware of every bit of code that might change the state of a given object. If you are working on a large code base it can be nearly impossible to keep track of this information. If all classes are immutable, this is a non-issue. Also, multi-threading becomes trivial.