Assignment 2 Clarifications

June 10, 2008

Part 1 (Reversing BST)

• The argument root passed into reverse can be None


Part 2 (Grid Generated Expressions)

• All integers in the grid will be non-negative (i.e., greater than or equal to 0)
• The grid may have the same integer in different positions. When tracing a path through the grid, you're not allowed to visit positions previously visited, but you are allowed to visit new positions that may have the same integer as in a previously visited position.
  
• All operands in an expression will be non-negative. (Note: The expression may still evaluate to a negative number. For example "3-5")
• A "well-formed expression" either
  
• contains no operands (i.e., this is the empty expression "")
  
• contains exactly 1 operand by itself (e.g., "5")
• or consists of an operand, followed by + or -, followed by a well-formed expression that contains at least 1 operand. (e.g. "5+5-10+6")
• A number grid of dimension n x n is permissable for any n >= 0. Examples:
  
• The empty list [] is a number grid with dimension 0 x 0
  
• [[3]] is a number grid with dimension 1 x 1
• [[3,2],[2,3]] is a number grid with dimension 2 x 2
• An expression with no operands (i.e., the empty expression "") evaluates to 0, and an expression with exactly 1 operand evaluates to the value of the operand.
  
• The empty expression "", which contains 0 operands, is a G-generated expression for any grid G.