Binary expression tree node with two possible states

Question

I am building out a binary expression tree and shown below is an implementation of the tree's node.

The node can be either a leaf or non-leaf, with leaves having Integer type values and non-leaves having ExpressionTreeNodeOperands type values. Leaves may have neither left nor right child nodes, and non-leaves must have both left and right child nodes.

I feel like this could be solved more appropriately using inheritance but can't seem to wrap my head around the generic Object member.

public class ExpressionTreeNode {

    private Object value;
    private ExpressionTreeNode leftNode;
    private ExpressionTreeNode rightNode;

    public ExpressionTreeNode(Object value) {
        this(value, null, null);
    }

    public ExpressionTreeNode(Object value, ExpressionTreeNode leftNode, ExpressionTreeNode rightNode) {

        if (value == null || (!(value instanceof Integer) && !(value instanceof ExpressionTreeNodeOperands))) {
            throw new IllegalArgumentException("Illegal argument: value must be non-null with a type of Integer or ExpressionTreeNodeOperand");
        }

        if (leftNode == null && rightNode != null || leftNode != null && rightNode == null) {
            throw new IllegalStateException("Illegal state: leftNode and rightNode should both be null or non-null alike");
        }

        if ((value instanceof Integer) && (leftNode != null && rightNode != null)) {
            throw new IllegalStateException("Illegal state: non-operand non-leaf node");
        }

        if (!(value instanceof Integer) && leftNode == null && rightNode == null) {
            throw new IllegalStateException("Illegal state: non-integer leaf node");
        }

        this.value = value;
        this.leftNode = leftNode;
        this.rightNode = rightNode;
    }

    public boolean isLeafNode() {
        return (leftNode == null) && (rightNode == null);
    }

    public Object getValue() {
        return value;
    }

    public ExpressionTreeNode getLeftNode() {
        return leftNode;
    }

    public ExpressionTreeNode getRightNode() {
        return rightNode;
    }
}

Answer 1

This is a perfect situation to introduce an interface. What you want to model is a tree-like structure, with nodes having a left and right subtree and leaf containing an integer value.

---

Your current code models this by having a single ExpressionTreeNode class, handling both cases of having a node with a left and right operand, and a leaf. What shows that this class has too much responsibility is the overhead you need to have to ensure its consistency:

if (value == null || (!(value instanceof Integer) && !(value instanceof ExpressionTreeNodeOperands))) {
    throw new IllegalArgumentException("Illegal argument: value must be non-null with a type of Integer or ExpressionTreeNodeOperand");
}

if (leftNode == null && rightNode != null || leftNode != null && rightNode == null) {
    throw new IllegalStateException("Illegal state: leftNode and rightNode should both be null or non-null alike");
}

if ((value instanceof Integer) && (leftNode != null && rightNode != null)) {
    throw new IllegalStateException("Illegal state: non-operand non-leaf node");
}

if (!(value instanceof Integer) && leftNode == null && rightNode == null) {
    throw new IllegalStateException("Illegal state: non-integer leaf node");
}

That is a lot of code to make sure that the node has a proper state after its construction. It also makes assumptions on the given arguments (namely, that you cannot pass a value that isn't an Integer or a ExpressionTreeNodeOperands): this is reasonable when well-documented but such constraints, if possible, would be preferable to ensure at compile-time.

For example, it will also compile if the caller gives an integer value along with a node, only to fail at run-time because it is incorrect.

---

The model you want to have here shows that, in fact, 3 classes need to be introduced:

• an ExpressionTree interface, that represents the tree-like structure.
• an ExpressionTreeNodeOperands class that would represent a node in the tree. A node would have 2 members: a left and a right subtree, represented as two members of type ExpressionTree.
• a Leaf class that would represent a leaf in the tree. This class would just have one member of type int.

A sample code would be the following:

interface ExpressionTree {
    boolean isLeaf();
}

class ExpressionTreeNodeOperands implements ExpressionTree {

    private ExpressionTree left;
    private ExpressionTree right;

    public ExpressionTreeNodeOperands(ExpressionTree left, ExpressionTree right) {
        this.left = Objects.requireNonNull(left);
        this.right = Objects.requireNonNull(right);
    }

    @Override
    public boolean isLeaf() {
        return false;
    }

}

class Leaf implements ExpressionTree {

    private int value;

    public Leaf(int value) {
        this.value = value;
    }

    @Override
    public boolean isLeaf() {
        return true;
    }

}

Notice a couple of things:

• Leaf is now constructed directly with an int and you cannot construct it without one. Also, it is not a boxed Integer: null values were not permitted before and are simply not possible now.
• ExpressionTreeNodeOperands is constructed with two arguments: the left and right sub-tree, which could be another ExpressionTreeNodeOperands, or a Leaf. It also calls requireNonNull to make sure that the given arguments are non-null.

The concern are now clearly separated: the node handles only its sub-trees, and the leaf handles only its value.

With this base, you can add convenience methods, like isLeaf, that would always return false for a node, and always return true for a leaf.

---

Then, depending on your actual usage, you may not even need a getLeft() and getRight() getters to retrieve the left and right node sub-trees. Let's take an example usage where we want to perform an infix traversal. You could add a String infix(); method inside the interface ExpressionTree, that would return a String representation:

@Override
public String infix() {
    return "(" + left.infix() + "," + right.infix() + ")";
}

for a node, and

@Override
public String infix() {
    return String.valueOf(value);
}

for a leaf. And then you can have:

ExpressionTree tree = new ExpressionTreeNodeOperands(new ExpressionTreeNodeOperands(new Leaf(2), new Leaf(1)), new Leaf(3));
System.out.println(tree.infix()); // prints ((2,1),3)