Finding the weight of the heaviest path in a binary tree

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:

• Terminology - is there a name for this problem? have I used

conventional names for things?

• Correctness - are there any bugs?

• Java conventions and idioms - can I make better use of the standard

libraries?

• Runtime performance.

• 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));
    }

}

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));
        }
    }
}

StackExchange Code Review Q#68589, answer score: 5