Build an Expression Tree from Postfix
Updated
Problem statement
Construct a binary expression tree from the valid postfix expression postfix. Each lowercase English letter becomes a leaf node. Each of +, -, *, / and ^ is a binary operator: its first popped subtree is its right child and its second popped subtree is its left child.
For this exercise, assume the function returns the constructed tree as fully parenthesized infix text. Write a leaf as its letter. Write an operator node as (left operator right), without spaces. Keep the parentheses around every operator node, even when the usual operator rules would allow you to leave some out. This function constructs and serializes the tree; it does not numerically evaluate operands.
Function
expressionTreeInfix(postfix: String) → StringExamples
Example 1
postfix = "ab+c*"return = "((a+b)*c)"The plus node has leaves a and b. The final multiplication uses that subtree as its left child and c as its right child.
Example 2
postfix = "ab-c/"return = "((a-b)/c)"Pop the right subtree first. Reversing pop order would incorrectly construct c divided by b minus a.
Constraints
- For this exercise, assume the postfix string has an odd length from 1 through 999.
- The expression is valid, contains no whitespace, and uses single-letter operands and the five listed binary operators.
- Operand letters may repeat and still represent separate leaf nodes.
More PeopleStrong Phone Screen questions
- Reverse Linked-List Nodes in Groups of KOA · PHONE SCREEN · Seen Mar 2026
- Level of the Minimum-Sum SubtreePHONE SCREEN · Seen Jan 2026
- Ceiling Value in a Sorted ArrayPHONE SCREEN · Seen Sep 2025
- Maximum Employee Salary for a CompanyPHONE SCREEN · Seen Sep 2025
- Valid ParenthesesPHONE SCREEN · Seen Sep 2025
- Number of ProvincesPHONE SCREEN · Seen May 2025
- Shortest Subarray with an Exact Target SumPHONE SCREEN · Seen May 2025
- Add Forward Linked-List Numbers Using RecursionPHONE SCREEN · Seen Oct 2021
- Running Median of a StreamPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2021
- Maximum Score from Deleting Neighboring ValuesPHONE SCREEN · Seen Oct 2021
Similar questions at other companies
- Ternary Expression to Binary TreeNutanix · ONSITE INTERVIEWNutanix interview questions
- Remove Parentheses from a Plus-Minus ExpressionOracle · PHONE SCREENOracle interview questions
- Decode StringCompass International Holdings · PHONE SCREENCompass International Holdings interview questions
- Calculator with ParenthesesGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- Flatten a Nested Object Into Dot KeysAdobe · PHONE SCREENAdobe interview questions
- Decode StringSambaNova Systems · PHONE SCREENSambaNova Systems interview questions
- Plus and Minus CalculatorIndeed · PHONE SCREENIndeed interview questions
- Construct a Tree from Level-Order and Inorder TraversalsAmazon · PHONE SCREEN
- Arithmetic Expression EvaluatorMicrosoft · PHONE SCREENMicrosoft interview questions
- Recover a Tree from Preorder Depth EncodingSuperhuman · PHONE SCREENSuperhuman interview questions