Evaluate Arithmetic tree

Fig1: Expression Tree

An expression tree is a special kind of binary tree that can be used to represent arithmetic expressions

The arithmetic expression is shown using three notations: infix, postfix, or prefix.

In most cases, when expression tree’s questions are given, one of the following is true;

• An image of the expression tree is given
• The postfix notation of the expression tree is given
• The infix and prefix notations of the expression tree are given.

In this article, we will see how we can evaluate an expression tree when given any of the elements above.

Formulated as postfix

If given a graph like Fig1, we can use the binary tree post-order traversal to evaluate the postfix notation. This traversal technique uses the following steps

• We start traversing the left subtree and call an ordering function recursively
• Next, we traverse the right subtree and call an ordering function recursively
• Finally, we visit the root node

If we follow the steps above, then we shall have: 3 2 + 4 5 + *

With this, the eval function alone won’t work. We may use many other techniques, but the one that works for me is using the Stack datastructure.

Fig2: Stack

From Fig2 above, we push into the stack if the value is a number. If the value is an operator, pop two values from the stack and evaluate, then push the resulting value into the stack.

class Stack:
    def __init__(self) -> None:
        self.data = []

    def push(self, item):
        self.data.append(item)

    def pop(self):
        return self.data.pop()

def evaluate(notation: str):
    stack = Stack()
    exp = notation.split()
    for item in exp:
        if item in "/*+-":
            left_operand = stack.pop()
            right_operand = stack.pop()
            value = eval(f'{left_operand} {item} {right_operand}')
            stack.push(value)
        else:
            stack.push(item)

    return int(stack.pop())

evaluate('3 2 + 4 5 + *') # 45

Formulated as infix and prefix

If all what we are given is the in-order and pre-order, then we can rebuild the tree from these two sequences, then evaluate the tree.

From Fig1, the following could be given.

• in-order: 3 + 2 * 4 + 5
• pre-order: * + 3 2 + 4 5

With this, it may be tempting to use the eval function on the in-order and expect to have the right answer.

eval('3 + 2 * 4 + 5') # 16

We see that it doesn’t give us the expected answer. Those with knowledge in order of operations and BODMAS specifically, will understand why.

So, having just the infix is not enough to evaluate an arithmetic tree.

How do we use both the inorder and preorder to rebuild an expression tree. At any point in time, we need to know the root , left subtree and right subtree .

• The root can be gotten from the preorder since the first element is always the root.
• The left subtree and right subtree can be gotten from the inorder since they are separated by the root.

from typing import Union

class Node:
    def __init__(self, data: int | str) -> None:
        self.data = data
        self.left_child: Union["Node", None] = None
        self.right_child: Union["Node", None] = None

def reconstruct(preorder: list[int | str], inorder: list[int | str]) -> Node | None:
    if not preorder and not inorder:
        return None
    if len(preorder) == len(inorder) == 1:
        return Node(preorder[0])

    root = Node(preorder[0])

    root_i = inorder.index(root.data)

    root.left_child = reconstruct(preorder[1: root_i + 1], inorder[0: root_i])
    root.right_child = reconstruct(preorder[root_i+1:], inorder[root_i+1:])

    return root

Here is an illustration of how the reconstruct function works;

• in-order: 3 + 2 * 4 + 5
• pre-order: * + 3 2 + 4 5

Fig3: Reconstruction

Once we have rebuilt the expression tree, we can proceed in two ways

• Evaluate the expression tree
• Evaluate post-order sequence of the expression tree

Evaluate the expression tree

Here, we will build a function that will evaluate the expression tree.

def calc(node):
    if str(node.data) in "/*-+":
        return eval(f"{calc(node.left_child)}{node.data}{calc(node.right_child)}")
    else:
        return node.data

To put things together,

inorder = "3 + 2 * 4 + 5"
preorder = "* + 3 2 + 4 5"

root_node = reconstruct(preorder.split(), inorder.split())
calc(root_node) # 45

Evaluate post-order sequence of the expression tree

We can generate the Postfix notation of the expression tree by performing a post-order traversal of the tree. Then, we apply the evaluate function created in the Formulated as postfix section above.

Post-order tree traversal works as follows

• Traverse the left subtree and call an ordering function recursively
• Next, traverse the right subtree and call an ordering function recursively
• Finally, visit the root node

result = []
def get_postorder(root_node):
    current = root_node
    if current is None:
        return
    get_postorder(current.left_child)
    get_postorder(current.right_child)
    result.append(str(current.data))

To put things together;

inorder = "3 + 2 * 4 + 5"
preorder = "* + 3 2 + 4 5"
result = []

def get_postorder(root_node):
    current = root_node
    if current is None:
        return
    get_postorder(current.left_child)
    get_postorder(current.right_child)
    result.append(str(current.data))

root_node = reconstruct(preorder.split(), inorder.split())
get_postorder(root_node) # ['3', '2', '+', '4', '5', '+', '*']

evaluate(' '.join(result)) # 45