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

• coderodde: Nice post! And welcome to Code Review! We are glad we have a Sloth in the house. :)

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)

• Sloth Armstrong: Thanks so much for the help, this is starting to make more sense. One thing that isn't addressed here is that the ExpressionTreeNodeOperands and Leaf classes both have values, ExpressionTreeNodeOperands has an enum value and Leaf has an int. Using the interface how can I implement getters for these values since they are of different types? Thanks again!
• Tunaki: @SlothArmstrong I would argue that you probably don't need such getter: once the tree is built, what would the caller do with the value alone? It is used to perform an operation, which means the tree will delegate the operation to Leaf or ExpressionTreeNodeOperands. In any case, if you do want it, one possibility that I see is to parameterize the tree with ExpressionTree<T>, and add a T value(); method.