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: ```python 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`. ```hint Decide when a node is ready Ask what a node needs to know about its children before it can decide whether it can be folded or removed, and let that decide the order in which you visit nodes. ``` ### 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? ### What a Strong Answer Covers - A rule set and node representation agreed before coding, with the baseline rules implemented exactly - A traversal that simplifies operands before their operator, so cascading simplifications are caught in one pass - Correct treatment of the non-commutative `-` operator (for example, `0 - x` is not `x`) - A clear decision on mutating versus rebuilding the tree, including reuse of unchanged subtrees - Time and space complexity, plus the recursion-depth risk for skewed trees - Tests covering constant-only, variable-only, mixed and cascading cases ### Follow-up Questions - Print the simplified tree as a string using the fewest parentheses that preserve its meaning, given operator precedence and the left-associativity of `-`. - Extend the simplifier to combine like terms so that `x + x` becomes `2 * x` and `2 * x + 3 * x` becomes `5 * x`. What representation makes this easier than rewriting the tree? - Add integer division. Which of your identities stop being safe, and what should happen to a subexpression that divides by zero? - The tree is a left-leaning chain of one million nodes. What fails in a recursive solution, and how do you make the traversal iterative?