171. What is an expression tree and how do you build one from a postfix expression?
MediumTrees
Technical
Show model answer
An expression tree has operands at the leaves and operators at internal nodes, with each operator's children being its operands. Inorder traversal (with parentheses) gives infix, preorder gives prefix and postorder gives postfix; evaluation is a post-order computation.
From postfix, use a stack of nodes: push a leaf for each operand; for an operator, pop the right child then the left, create the operator node with them, and push it. The last node left is the root. Building and evaluating are O(n) time and O(n) space. Compilers use the same idea for abstract syntax trees.