Hi, here’s your problem today. This problem was recently 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.

Example:

```
*
/ \
+ +
/ \ / \
3 2 4 5
```

This is a representation of the expression (3 + 2) * (4 + 5), and should return 45.

Here’s a starting point:

```
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
PLUS = "+"
MINUS = "-"
TIMES = "*"
DIVIDE = "/"
def evaluate(root):
# Fill this in.
tree = Node(TIMES)
tree.left = Node(PLUS)
tree.left.left = Node(3)
tree.left.right = Node(2)
tree.right = Node(PLUS)
tree.right.left = Node(4)
tree.right.right = Node(5)
print evaluate(tree)
# 45
```