Design an Expression Tree With Evaluate Function

Design an Expression Tree With Evaluate Function - Problem

Array Math Stack Tree Design Binary Tree Medium

Given the postfix tokens of an arithmetic expression, build and return the binary expression tree that represents this expression.

Postfix notation is a notation for writing arithmetic expressions in which the operands (numbers) appear before their operators. For example, the postfix tokens of the expression 4*(5-(7+2)) are represented in the array postfix = ["4","5","7","2","+","-","*"].

The class Node is an interface you should use to implement the binary expression tree. The returned tree will be tested using the evaluate function, which is supposed to evaluate the tree's value.

A binary expression tree is a kind of binary tree used to represent arithmetic expressions. Each node of a binary expression tree has either zero or two children. Leaf nodes (nodes with 0 children) correspond to operands (numbers), and internal nodes (nodes with two children) correspond to the operators '+' (addition), '-' (subtraction), '*' (multiplication), and '/' (division).

It's guaranteed that no subtree will yield a value that exceeds 10⁹ in absolute value, and all the operations are valid (i.e., no division by zero).

Follow up: Could you design the expression tree such that it is more modular? For example, is your design able to support additional operators without making changes to your existing evaluate implementation?

Input & Output

Example 1 — Basic Expression

$ Input: postfix = ["3","4","+","2","*"]

› Output: 14

💡 Note: The expression is (3 + 4) * 2 = 7 * 2 = 14. First we add 3 and 4, then multiply by 2.

Example 2 — Division and Subtraction

$ Input: postfix = ["4","5","+","6","7","+","-","2","/"]

› Output: -3

💡 Note: The expression is ((4 + 5) - (6 + 7)) / 2 = (9 - 13) / 2 = -4 / 2 = -2. Wait, let me recalculate: (9 - 13) / 2 = -4 / 2 = -2, but integer division gives -2, not -3. Actually: 9 - 13 = -4, then -4/2 = -2.

Example 3 — Single Number

$ Input: postfix = ["15"]

› Output: 15

💡 Note: Single operand case: the tree has only one node containing 15, so the result is 15.

Constraints

1 ≤ postfix.length ≤ 100
postfix[i] is either an integer or one of '+', '-', '*', '/'
All integers are in range [-100, 100]
The given expression is always valid
The result and all intermediate calculations fit in 32-bit integers

Visualization

Tap to expand

Understanding the Visualization

Input

Postfix tokens: ["3","4","+","2","*"]

Process

Stack-based tree construction from left to right

Output

Binary tree that evaluates to 14

Key Takeaway

🎯 Key Insight: Stack naturally processes postfix expressions by handling operands and operators in the correct order for tree construction

Asked in

G Google 25 M Microsoft 18 a Amazon 15 Apple 12

The key insight is using a stack to build the expression tree from postfix notation. When we encounter operands, we create leaf nodes. When we encounter operators, we pop two nodes from the stack as children and create a new internal node. The optimal approach uses modular design with abstract Node interface for easy extensibility. Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized Stack with Modular Design	O(n)	O(n)	Use stack construction with abstract Node interface for extensibility
Brute Force Stack Construction	O(n)	O(n)	Use basic stack to build expression tree with simple node structure

Optimized Stack with Modular Design — Algorithm Steps

Define abstract Node interface with evaluate method
Create OperatorNode and OperandNode classes
Use stack to build tree with polymorphic nodes
Evaluation uses polymorphism for each node type

Visualization

Tap to expand

Step-by-Step Walkthrough

Node Interface

Abstract Node with evaluate() method

Concrete Classes

OperandNode and OperatorNode implement interface

Polymorphic Tree

Tree built with different node types, evaluation uses polymorphism

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

typedef enum {
    OPERAND,
    OPERATOR
} NodeType;

typedef struct Node {
    NodeType type;
    union {
        int value;
        struct {
            char op;
            struct Node* left;
            struct Node* right;
        } operation;
    } data;
} Node;

Node* createOperandNode(int value) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->type = OPERAND;
    node->data.value = value;
    return node;
}

Node* createOperatorNode(char op, Node* left, Node* right) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->type = OPERATOR;
    node->data.operation.op = op;
    node->data.operation.left = left;
    node->data.operation.right = right;
    return node;
}

int evaluate(Node* node) {
    if (node->type == OPERAND) {
        return node->data.value;
    }
    
    int leftVal = evaluate(node->data.operation.left);
    int rightVal = evaluate(node->data.operation.right);
    
    switch (node->data.operation.op) {
        case '+': return leftVal + rightVal;
        case '-': return leftVal - rightVal;
        case '*': return leftVal * rightVal;
        case '/': return leftVal / rightVal;
    }
    
    return 0;
}

Node* solution(char postfix[][20], int size) {
    Node* stack[1000];
    int top = -1;
    
    for (int i = 0; i < size; i++) {
        Node* node;
        if (strlen(postfix[i]) == 1 && strchr("+-*/", postfix[i][0])) {
            Node* right = stack[top--];
            Node* left = stack[top--];
            node = createOperatorNode(postfix[i][0], left, right);
        } else {
            node = createOperandNode(atoi(postfix[i]));
        }
        
        stack[++top] = node;
    }
    
    return stack[0];
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    char postfix[100][20];
    int size = 0;
    
    char* token = strtok(line, "[],\"");
    while (token != NULL && size < 100) {
        if (strlen(token) > 0 && strcmp(token, " ") != 0) {
            strcpy(postfix[size++], token);
        }
        token = strtok(NULL, "[],\"");
    }
    
    Node* root = solution(postfix, size);
    printf("%d\n", evaluate(root));
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through n tokens, each stack operation is O(1)

✓ Linear Growth

Space Complexity

O(n)

Stack holds up to n nodes, tree structure requires O(n) space for all nodes

⚡ Linearithmic Space

31.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized Stack with Modular Design — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler