QUESTION 13
What is an expression tree?
2 marksAnswer
It is a tree with operands at leaves and operators at internal nodes. For binary operators, each operator has a left and right operand subtree.
QUESTION 14
Explain expression trees, construction from postfix and traversals.
5 marksAnswer in brief
An expression tree stores the structure of a calculation explicitly rather than relying only on a linear expression string.
Postfix construction
- Create a leaf and push its pointer for every operand.
- For a binary operator, pop the right subtree first, then the left.
- Create an operator node with those children and push it.
- Require one final tree root; reject insufficient operands or leftover roots.
Example
For postfix AB+C*, first make leaves A and B and combine them under +. Then create C. Finally make * the root, with the + subtree on its left and C on its right. The tree represents (A+B)*C.
Traversals
Preorder visits root, left and right, producing *+ABC. Postorder visits left, right and root, producing AB+C*. Inorder visits left, root and right. To preserve exact expression grouping, include suitable parentheses; plain unparenthesised inorder text can lose the tree’s grouping.
Evaluation
For a leaf, obtain its operand value. For an operator node, evaluate its left and right subtrees and apply the operator with valid arithmetic. Reject zero division and out-of-range calculations according to the chosen numeric representation.
Complexity
Construction from n tokens uses O(n) node and stack space and O(n) structural work. Traversal visits each node once: O(n) time. Recursive traversal adds O(h) call depth for tree height h. Dynamically created nodes must be released when the tree is no longer needed.
Diagram or flowchart
