Hands-On Data Structures and Algorithms with Python - Second Edition

Expression trees

An arithmetic expression is represented by a combination of operators and operands where the operators can be unary or binary. An arithmetic expression can also be represented using a binary tree, which is called an expression tree. This tree structure can also be used to parse arithmetic and boolean expressions. In an expression tree, all the leaf nodes contain the operands and non-leaf nodes contain the operators. We should also note that the expression tree will have one of its sub-trees (right sub-tree or left sub-tree) empty in the case of a unary operator.

For example, the expression tree for 3 + 4 would look as follows:

For a slightly more complex expression, (4 + 5) * (5-3), we would get the following:

The arithmetic ...