This problem was asked by Apple.
You are given a binary tree representation of an arithmetic expression. In this tree, each leaf is an integer value, and a non-leaf node is one of the four operations: '+', '-', '*', or '/'.
Write a function that takes this tree and evaluates the expression.
Input:
*
/ \
+ +
/ \ / \
3 2 4 5
Output:
45 # (3 + 2) * (4 + 5)