Skip to interview prep
Apexed

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.

What is an expression tree and how do you build one from a postfix expression — Data structures & algorithms interview question — Apexed