CodeWorkout
  1. Home
  2. Gym
  3. Final - IN-CLASS Practice
  4. X1494: validExpressionTree

X1494: validExpressionTree

An expression tree is a binary tree with numbers (e.g., 10, 5, 20) in the leaf (terminal) nodes and operators (+,/,*,-) in the internal nodes. Write a recursive routine that returns true if an expression tree is valid according to the definition given above.

An expression tree is valid, if and only if:

  • it is a full tree
  • all terminal nodes have numbers
  • all internal nodes have operators
  • an empty tree is not valid

ExpressionNode

ExpressionNode is very similar to BinaryNode<String> but it is does not use generic types. It always stores a String value in the node. It has two additional methods to make your solution simpler:

  • isNumeric() returns true if the value stored in the node is a valid number
  • isOperator() returns true if the value stored in the node is a valid operator (e.g., +, /)

The class definition is below:

public class ExpressionNode {
    private String value;
    private ExpressionNode left;
    private ExpressionNode right;

    // constructors and setters hidden for brevity

    ExpressionNode getLeft() { return left; }
    ExpressionNode getRight() { return right; }

    boolean isNumeric()
    { ... } // returns true if value is numeric

    boolean isOperator() 
    { ... } // returns true if value is an operator
}

To Do

Write a recursive method boolean validExpressionTree(ExpressionNode root) that returns true if the tree passed in root is valid as defined above or false otherwise. Make use of getLeft(), getRight(), to traverse the tree and isNumeric() and isOperator() to see if the nodes have the appropriate value.

Your Answer:

Reset
Next exercise

Feedback

Your feedback will appear here when you check your answer.