Evaluate an expression tree and generate a parenthesised form

Problem

Given an expression tree, evaluate the arithmetic expression represented by the tree, and produce its fully parenthesised form. An expression tree is a binary tree in which:

1. Each leaf node contains an operand (integer).
2. Each internal (non-leaf) node contains an operator (+, -, *, or /).

Your task is to evaluate both:

1. The result of the arithmetic expression.
2. Its parenthesised form.

Examples

Example 1

 Input: 
     Tree structure: 
         *
        / \
       +   5
      / \
     2   3
 
 Output:
     Result: 25
     Parenthesised form: ((2 + 3) * 5)
 
 Explanation:
     First, evaluate the subtree `2 + 3` which results in `5`. 
     Then evaluate `5 * 5` which results in `25`.

Example 2

 Input: 
     Tree structure: 
         -
        / \
       *   4
      / \
     7   3
 
 Output:
     Result: 17
     Parenthesised form: ((7 * 3) - 4)
 
 Explanation:
     First, evaluate the subtree `7 * 3` which results in `21`. 
     Then evaluate `21 - 4` which results in `17`.

Example 3

 Input: 
     Tree structure:
         /
        / \
       8   2
 
 Output:
     Result: 4
     Parenthesised form: (8 / 2)
 
 Explanation:
     Direct division `8 / 2` evaluates to `4`.

Solution

Method 1 - Recursion

In an expression tree, leaf nodes contain operands (e.g., integers), and internal nodes represent operators (e.g., +, -, *, /). Evaluation proceeds in a recursive post-order traversal (evaluate left and right subtrees first, and then apply the operator on the results).

Construct the parenthesised form by recursively combining the sub-expressions in the required format while traversing the tree.

Approach

1. Recursive Tree Traversal:
   • Use post-order traversal for both evaluation and building the parenthesised expression.
   • If the current node is an operator, perform the operation on the results from the left and right subtrees.
   • If it's a leaf node, simply return the operand.
2. Implementation Steps:
   • Write helper methods to evaluate the expression and produce the parenthesised form.
   • Traverse the tree recursively:
     • For leaf nodes, return their value.
     • For internal nodes, recursively evaluate child nodes and combine results based on the operator.
3. Assumptions:
   • The tree is a valid expression tree.
   • Division / produces integer results (floor division for Python, integer division for Java).

Code

Java

class TreeNode {
    int val;
    TreeNode left, right;

    TreeNode(int val) {
        this.val = val;
        this.left = this.right = null;
    }
}

class Solution {
    public static class ResultPair {
        int result;
        String parenthesised;

        ResultPair(int result, String parenthesised) {
            this.result = result;
            this.parenthesised = parenthesised;
        }
    }

    public ResultPair evaluateExpressionTree(TreeNode root) {
        if (root == null) return new ResultPair(0, "");

        // Leaf node case
        if (root.left == null && root.right == null) {
            return new ResultPair(root.val, Integer.toString(root.val));
        }

        // Evaluate left and right subtrees
        ResultPair left = evaluateExpressionTree(root.left);
        ResultPair right = evaluateExpressionTree(root.right);

        int result = 0;
        String parenthesised = "";
        String operator = Integer.toString(root.val);

        // Perform the operation
        switch (operator) {
            case "+":
                result = left.result + right.result;
                break;
            case "-":
                result = left.result - right.result;
                break;
            case "*":
                result = left.result * right.result;
                break;
            case "/":
                result = left.result / right.result;
                break;
        }

        parenthesised = "(" + left.parenthesised + " " + operator + " " + right.parenthesised + ")";
        return new ResultPair(result, parenthesised);
    }
}

Python

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.val = value
        self.left = left
        self.right = right

class Solution:
    def evaluateExpressionTree(self, root):
        if not root:
            return 0, ""

        # If it's a leaf node, return the operand and its string form directly
        if not root.left and not root.right:
            return int(root.val), str(root.val)

        # Recursively evaluate left and right children
        left_val, left_expr = self.evaluateExpressionTree(root.left)
        right_val, right_expr = self.evaluateExpressionTree(root.right)

        # Perform the operation based on current node's value
        operator = root.val
        if operator == '+':
            result = left_val + right_val
        elif operator == '-':
            result = left_val - right_val
        elif operator == '*':
            result = left_val * right_val
        elif operator == '/':
            result = left_val // right_val  # Integer division

        parenthesised = f"({left_expr} {operator} {right_expr})"
        return result, parenthesised

Complexity

• ⏰ Time complexity: O(n) where n is the number of nodes in the tree (each node is visited once).
• 🧺 Space complexity: O(h) where h is the height of the tree (maximum recursion stack depth).