ArithmeticBinaryTree.py

'''
Arithmetic Binary Tree

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.
'''
from typing import *

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

PLUS = "+"
MINUS = "-"
TIMES = "*"
DIVIDE = "/"

def evaluateExpressionroot(root):
    ans = 0
    if root:
        if root.left and root.right:
            leftA = evaluateExpressionroot(root.left)
            rightA = evaluateExpressionroot(root.right)
            if root.val == PLUS:
                ans = leftA + rightA
            elif root.val == MINUS:
                ans = leftA - rightA
            elif root.val == TIMES:
                ans = leftA * rightA
            elif root.val == DIVIDE:
                ans = leftA / rightA
        else:
            ans = root.val
    return ans

root = Node(TIMES)
root.left = Node(PLUS)
root.left.left = Node(3)
root.left.right = Node(2)
root.right = Node(PLUS)
root.right.left = Node(4)
root.right.right = Node(5)
print(evaluateExpressionroot(root))
# 45

root = Node(PLUS) 
root.left = Node(TIMES) 
root.left.left = Node(5) 
root.left.right = Node(4) 
root.right = Node(MINUS) 
root.right.left = Node(100) 
root.right.right = Node(20) 
print(evaluateExpressionroot(root))
#100

root = Node(PLUS) 
root.left = Node(TIMES) 
root.left.left = Node(5) 
root.left.right = Node(4) 
root.right = Node(MINUS) 
root.right.left = Node(100) 
root.right.right = Node(DIVIDE) 
root.right.right.left = Node(20) 
root.right.right.right = Node(2) 
print(evaluateExpressionroot(root))
#110