Given a simple expression tree, consisting of basic binary operators i.e., + , – ,* and / and some integers, evaluate the expression tree.
As all the operators in the tree are binary hence each node will have either 0 or 2 children. As it can be inferred from the examples above , the integer values would appear at the leaf nodes , while the interior nodes represent the operators.
To evaluate the syntax tree , a recursive approach can be followed .
Algorithm : Let t be the syntax tree If t is not null then If t.info is operand then Return t.info Else A = solve(t.left) B = solve(t.right) return A operator B where operator is the info contained in t
The time complexity would be O(n), as each node is visited once. Below is a C++ program for the same:
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
This article is attributed to GeeksforGeeks.org