Problem

Given a simple expression tree, consisting of basic binary operators i.e., + , – , * and / and some integers, evaluate the expression tree.

Examples

Example 1:

graph TD;
A(+) --- B(*) & C("-")
B --- D(5) & E(4)
C --- F(100) & G(20)
  
Input: root = ["+", "*", "-", "5", "4", "100", "20"]
Output: 100

**Example 2:

graph TD;
A(+) --- B(*) & C("-")
B --- D(5) & E(4)
C --- F(100) & G("/")
G --- H(20) & I(2)
  
Input: root = ["+", "*", "-", "5", "4", "100", "/", null, null, null, null, null, null, "20", "2"]
Output: 110

Solution

Method 1 - Recursive Postorder

The leaf nodes are operands, and non-leaf nodes are operator. We can following logic:

  • If current node is leaf, then we return the parsed value
  • If it is not, then it is a binary operator, and we calculate the value and return to parent

So, we process the left and right children first, and then the parent.

Code

Java
public class TreeNode {
	String val;
	TreeNode left;
	TreeNode right;

	TreeNode(String x) {
		val = x;
	}
}


public class ExpressionTreeEvaluator {

	public int evaluate(TreeNode root) {
		// Base case: if the root is a leaf node (operand), return its integer value
		if (root.left == null && root.right == null) {
			return Integer.parseInt(root.val);
		}

		// Recursively evaluate the left and right subtrees
		int left = evaluate(root.left);
		int right = evaluate(root.right);

		// Apply the operator at the root to the values from the left and right subtrees
		switch (root.val) {
			case "+":
				return left + right;
			case "-":
				return left - right;
			case "*":
				return left * right;
			case "/":
				return left / right;
			default:
				throw new IllegalArgumentException("Invalid operator: " + root.val);
		}
	}

	public static void main(String[] args) {
		// Build the tree from the example
		TreeNode root = new TreeNode("+");
		root.left = new TreeNode("*");
		root.right = new TreeNode("/");

		root.left.left = new TreeNode("-");
		root.left.right = new TreeNode("100");

		root.left.left.left = new TreeNode("5");
		root.left.left.right = new TreeNode("4");

		root.right.left = new TreeNode("100");
		root.right.right = new TreeNode("20");

		// Evaluate the expression tree
		ExpressionTreeEvaluator evaluator = new ExpressionTreeEvaluator();
		int result = evaluator.evaluate(root);

		// Output the result
		System.out.println("The result of the expression tree is: " + result);
	}
}

Complexity

  • ⏰ Time complexity: O(n) - as we have to process all the n nodes
  • 🧺 Space complexity: O(h) - given the recursion stack