Simplify an Arithmetic Expression Tree with Constant Folding and Identities

You are given the root of a binary tree that is the abstract syntax tree (AST) of an arithmetic expression. Every internal node holds a binary operator and has exactly two children; every leaf holds either an integer constant or a variable name. Write a function that traverses the tree and returns an equivalent, simplified expression tree.

Assume the following node shape, and adapt it to your language:

class Node:
 def __init__(self, val, left=None, right=None):
 self.val = val # "+", "-" or "*" for internal nodes; an int or a variable name (str) for leaves
 self.left = left
 self.right = right

The interview report does not list the exact simplification rules, so agree on them with the interviewer before coding. As a baseline, assume your function must at least:

• fold any operator node whose two operands are both constants into a single constant; and
• apply the identities x + 0 = x, 0 + x = x, x - 0 = x, x * 1 = x, 1 * x = x, x * 0 = 0 and 0 * x = 0, where x is any subexpression;

and it must apply these rules everywhere in the tree, including where one simplification makes another one possible. For example, the tree for (x * 1) + (2 * 3) should become the tree for x + 6, and the tree for (y + 0) * (4 - 4) should become the single constant 0.

Clarifying Questions

• Which operators can appear? In particular, can there be division or unary minus, and if so, how should division by a constant zero be treated?
• Beyond the baseline, should the function combine like terms (for example x + x) or reassociate constants (for example (x + 2) + 3)?
• Should the input tree be left unmodified with a new tree returned, or may it be simplified in place?
• Is the expected output a tree, a printed string, or both? If a string, how should parentheses be handled?
• How deep can the tree be, and is recursion acceptable?