Expression Trees: Build, Evaluate & Reconstruct Infix

1. Introduction & Motivation

Given a postfix expression like 3 4 + 5 2 - *, a stack of numbers is enough to compute a single answer: push operands, and whenever an operator arrives, pop two numbers, combine them, and push the result. That approach is covered in Expression Evaluation and Infix to Postfix Conversion in Part 7 of this series — and it is genuinely the right tool when all you need is one numeric result.

But the moment the stack pops two numbers and pushes their sum, the fact that they came from separate subexpressions is gone forever. There is no way to ask "what were the two operands of the last addition?" or "can I rewrite this expression with $x$ replaced by 5?" after the stack has collapsed everything into a single value.

An expression tree fixes this by building an actual tree structure instead of collapsing to a number: every leaf holds an operand, every internal node holds an operator, and each internal node's two children are exactly the subexpressions it combines. Nothing is discarded. Once the tree exists, evaluating it is one traversal among many possible traversals — you can also print it back out as infix, differentiate it, simplify it, or hand it to a compiler as the first step of understanding source code.

2. Prerequisites

This lesson builds directly on two earlier parts of the series:

Infix to Postfix Conversion (Part 7) — the Shunting Yard algorithm that turns (3 + 4) * (5 - 2) into 3 4 + 5 2 - *. This lesson starts from that postfix output.
Expression Evaluation (Part 7) — the stack-of-numbers algorithm this lesson deliberately contrasts with: same token order, same push/pop pattern, but pushing and popping tree nodes instead of numbers.
Tree Fundamentals (Part 9) — basic binary tree structure and the preorder, inorder, and postorder traversals used throughout this lesson.

3. A Concrete Example

Worked Example

Building the tree for (3 + 4) * (5 - 2)

The infix expression (3 + 4) * (5 - 2) converts to postfix as 3 4 + 5 2 - *. Scan the postfix tokens left to right, keeping a stack of subtrees rather than numbers: an operand pushes a new leaf node, and an operator pops its two most recent subtrees and combines them into a new internal node.

Token	Action	Stack of subtrees (bottom → top)
`3`	Push leaf `3`	`[3]`
`4`	Push leaf `4`	`[3, 4]`
`+`	Pop `4`, pop `3`, push node `(3 + 4)`	`[(3+4)]`
`5`	Push leaf `5`	`[(3+4), 5]`
`2`	Push leaf `2`	`[(3+4), 5, 2]`
`-`	Pop `2`, pop `5`, push node `(5 - 2)`	`[(3+4), (5-2)]`
`*`	Pop `(5-2)`, pop `(3+4)`, push node `(3+4) * (5-2)`	`[(3+4)*(5-2)]`

After the last token, exactly one subtree remains on the stack: the root is *, its left child is the + subtree holding leaves 3 and 4, and its right child is the - subtree holding leaves 5 and 2. Evaluating that tree gives $(3+4) \times (5-2) = 7 \times 3 = 21$.

4. Core Insight

                Core insight: Building an expression tree from postfix mirrors postfix stack evaluation exactly — same scan, same push/pop pattern — except the stack holds tree nodes instead of numbers. An operand pushes a leaf node; an operator pops its two most recent subtrees and combines them into a new internal node labeled with that operator. Postfix order guarantees that by the time an operator is read, both of its operand subtrees have already been fully built and are sitting on top of the stack.
            

5. Building an Expression Tree from Postfix

Each panel below builds the tree for 3 4 + 5 2 - * and confirms the structure by printing a preorder traversal, which recovers the equivalent prefix form of the same expression.

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

OPERATORS = {"+", "-", "*", "/", "^"}

def build_expression_tree(postfix):
    stack = []
    for token in postfix.split():
        if token in OPERATORS:
            right = stack.pop()
            left = stack.pop()
            stack.append(Node(token, left, right))
        else:
            stack.append(Node(token))
    if len(stack) != 1:
        raise ValueError("malformed postfix expression")
    return stack.pop()

def preorder(node):
    if node is None:
        return []
    return [node.value] + preorder(node.left) + preorder(node.right)

tree = build_expression_tree("3 4 + 5 2 - *")
print(" ".join(preorder(tree)))  # * + 3 4 - 5 2

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <stdexcept>

struct Node {
    std::string value;
    Node* left;
    Node* right;
    Node(std::string v, Node* l = nullptr, Node* r = nullptr)
        : value(std::move(v)), left(l), right(r) {}
};

bool isOperator(const std::string& token) {
    return token == "+" || token == "-" || token == "*" || token == "/" || token == "^";
}

Node* buildExpressionTree(const std::string& postfix) {
    std::vector<Node*> stack;
    std::istringstream iss(postfix);
    std::string token;
    while (iss >> token) {
        if (isOperator(token)) {
            Node* right = stack.back(); stack.pop_back();
            Node* left = stack.back(); stack.pop_back();
            stack.push_back(new Node(token, left, right));
        } else {
            stack.push_back(new Node(token));
        }
    }
    if (stack.size() != 1) {
        throw std::invalid_argument("malformed postfix expression");
    }
    return stack.back();
}

void preorder(Node* node, std::vector<std::string>& tokens) {
    if (node == nullptr) return;
    tokens.push_back(node->value);
    preorder(node->left, tokens);
    preorder(node->right, tokens);
}

int main() {
    Node* tree = buildExpressionTree("3 4 + 5 2 - *");
    std::vector<std::string> tokens;
    preorder(tree, tokens);
    for (std::size_t i = 0; i < tokens.size(); ++i) {
        std::cout << tokens[i] << (i + 1 < tokens.size() ? ' ' : '\n');
    }
    // * + 3 4 - 5 2
}

import java.util.*;

class Node {
    String value;
    Node left, right;
    Node(String value) { this(value, null, null); }
    Node(String value, Node left, Node right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

public class ExpressionTreeBuilder {
    static final Set<String> OPERATORS = Set.of("+", "-", "*", "/", "^");

    static Node buildExpressionTree(String postfix) {
        Deque<Node> stack = new ArrayDeque<>();
        for (String token : postfix.split(" ")) {
            if (OPERATORS.contains(token)) {
                Node right = stack.pop();
                Node left = stack.pop();
                stack.push(new Node(token, left, right));
            } else {
                stack.push(new Node(token));
            }
        }
        if (stack.size() != 1) {
            throw new IllegalArgumentException("malformed postfix expression");
        }
        return stack.pop();
    }

    static void preorder(Node node, List<String> tokens) {
        if (node == null) return;
        tokens.add(node.value);
        preorder(node.left, tokens);
        preorder(node.right, tokens);
    }

    public static void main(String[] args) {
        Node tree = buildExpressionTree("3 4 + 5 2 - *");
        List<String> tokens = new ArrayList<>();
        preorder(tree, tokens);
        System.out.println(String.join(" ", tokens)); // * + 3 4 - 5 2
    }
}

6. Evaluating an Expression Tree

Evaluation is a simple postorder recursion: evaluate the left subtree, evaluate the right subtree, then apply the node's operator to the two results. A leaf evaluates to its own numeric value.

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

OPERATORS = {"+", "-", "*", "/", "^"}

def build_expression_tree(postfix):
    stack = []
    for token in postfix.split():
        if token in OPERATORS:
            right = stack.pop()
            left = stack.pop()
            stack.append(Node(token, left, right))
        else:
            stack.append(Node(token))
    return stack.pop()

def evaluate(node):
    if node.left is None and node.right is None:
        return float(node.value)
    left_value = evaluate(node.left)
    right_value = evaluate(node.right)
    if node.value == "+": return left_value + right_value
    if node.value == "-": return left_value - right_value
    if node.value == "*": return left_value * right_value
    if node.value == "/": return left_value / right_value
    if node.value == "^": return left_value ** right_value
    raise ValueError(f"unknown operator {node.value}")

tree = build_expression_tree("3 4 + 5 2 - *")
print("Result:", evaluate(tree))  # Result: 21.0

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <cmath>
#include <stdexcept>

struct Node {
    std::string value;
    Node* left;
    Node* right;
    Node(std::string v, Node* l = nullptr, Node* r = nullptr)
        : value(std::move(v)), left(l), right(r) {}
};

bool isOperator(const std::string& token) {
    return token == "+" || token == "-" || token == "*" || token == "/" || token == "^";
}

Node* buildExpressionTree(const std::string& postfix) {
    std::vector<Node*> stack;
    std::istringstream iss(postfix);
    std::string token;
    while (iss >> token) {
        if (isOperator(token)) {
            Node* right = stack.back(); stack.pop_back();
            Node* left = stack.back(); stack.pop_back();
            stack.push_back(new Node(token, left, right));
        } else {
            stack.push_back(new Node(token));
        }
    }
    return stack.back();
}

double evaluate(Node* node) {
    if (node->left == nullptr && node->right == nullptr) {
        return std::stod(node->value);
    }
    double leftValue = evaluate(node->left);
    double rightValue = evaluate(node->right);
    if (node->value == "+") return leftValue + rightValue;
    if (node->value == "-") return leftValue - rightValue;
    if (node->value == "*") return leftValue * rightValue;
    if (node->value == "/") return leftValue / rightValue;
    if (node->value == "^") return std::pow(leftValue, rightValue);
    throw std::invalid_argument("unknown operator " + node->value);
}

int main() {
    Node* tree = buildExpressionTree("3 4 + 5 2 - *");
    std::cout << "Result: " << evaluate(tree) << std::endl; // Result: 21
}

import java.util.*;

class Node {
    String value;
    Node left, right;
    Node(String value) { this(value, null, null); }
    Node(String value, Node left, Node right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

public class ExpressionTreeEvaluator {
    static final Set<String> OPERATORS = Set.of("+", "-", "*", "/", "^");

    static Node buildExpressionTree(String postfix) {
        Deque<Node> stack = new ArrayDeque<>();
        for (String token : postfix.split(" ")) {
            if (OPERATORS.contains(token)) {
                Node right = stack.pop();
                Node left = stack.pop();
                stack.push(new Node(token, left, right));
            } else {
                stack.push(new Node(token));
            }
        }
        return stack.pop();
    }

    static double evaluate(Node node) {
        if (node.left == null && node.right == null) {
            return Double.parseDouble(node.value);
        }
        double leftValue = evaluate(node.left);
        double rightValue = evaluate(node.right);
        switch (node.value) {
            case "+": return leftValue + rightValue;
            case "-": return leftValue - rightValue;
            case "*": return leftValue * rightValue;
            case "/": return leftValue / rightValue;
            case "^": return Math.pow(leftValue, rightValue);
            default: throw new IllegalArgumentException("unknown operator " + node.value);
        }
    }

    public static void main(String[] args) {
        Node tree = buildExpressionTree("3 4 + 5 2 - *");
        System.out.println("Result: " + evaluate(tree)); // Result: 21.0
    }
}

7. Inorder Traversal to Recover Infix

This is something a stack-based scan cannot do at all, because it never keeps the structure around once it produces a number. With a tree, an inorder traversal (left, node, right) reproduces the original operand order. Adding parentheses whenever a child's operator has lower precedence than its parent's operator reconstructs a fully-parenthesized infix expression, exactly recovering (3 + 4) * (5 - 2) from the tree built earlier.

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

OPERATORS = {"+", "-", "*", "/", "^"}
PRECEDENCE = {"+": 1, "-": 1, "*": 2, "/": 2, "^": 3}

def build_expression_tree(postfix):
    stack = []
    for token in postfix.split():
        if token in OPERATORS:
            right = stack.pop()
            left = stack.pop()
            stack.append(Node(token, left, right))
        else:
            stack.append(Node(token))
    return stack.pop()

def to_infix(node, parent_precedence=0):
    if node.left is None and node.right is None:
        return node.value
    my_precedence = PRECEDENCE[node.value]
    left_str = to_infix(node.left, my_precedence)
    right_str = to_infix(node.right, my_precedence)
    expression = f"{left_str} {node.value} {right_str}"
    if my_precedence < parent_precedence:
        return f"({expression})"
    return expression

tree = build_expression_tree("3 4 + 5 2 - *")
print(to_infix(tree))  # (3 + 4) * (5 - 2)

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <map>

struct Node {
    std::string value;
    Node* left;
    Node* right;
    Node(std::string v, Node* l = nullptr, Node* r = nullptr)
        : value(std::move(v)), left(l), right(r) {}
};

bool isOperator(const std::string& token) {
    return token == "+" || token == "-" || token == "*" || token == "/" || token == "^";
}

Node* buildExpressionTree(const std::string& postfix) {
    std::vector<Node*> stack;
    std::istringstream iss(postfix);
    std::string token;
    while (iss >> token) {
        if (isOperator(token)) {
            Node* right = stack.back(); stack.pop_back();
            Node* left = stack.back(); stack.pop_back();
            stack.push_back(new Node(token, left, right));
        } else {
            stack.push_back(new Node(token));
        }
    }
    return stack.back();
}

std::map<std::string, int> PRECEDENCE = {{"+", 1}, {"-", 1}, {"*", 2}, {"/", 2}, {"^", 3}};

std::string toInfix(Node* node, int parentPrecedence = 0) {
    if (node->left == nullptr && node->right == nullptr) {
        return node->value;
    }
    int myPrecedence = PRECEDENCE[node->value];
    std::string leftStr = toInfix(node->left, myPrecedence);
    std::string rightStr = toInfix(node->right, myPrecedence);
    std::string expression = leftStr + " " + node->value + " " + rightStr;
    if (myPrecedence < parentPrecedence) {
        return "(" + expression + ")";
    }
    return expression;
}

int main() {
    Node* tree = buildExpressionTree("3 4 + 5 2 - *");
    std::cout << toInfix(tree) << std::endl; // (3 + 4) * (5 - 2)
}

import java.util.*;

class Node {
    String value;
    Node left, right;
    Node(String value) { this(value, null, null); }
    Node(String value, Node left, Node right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

public class ExpressionTreeInfix {
    static final Set<String> OPERATORS = Set.of("+", "-", "*", "/", "^");
    static final Map<String, Integer> PRECEDENCE = Map.of("+", 1, "-", 1, "*", 2, "/", 2, "^", 3);

    static Node buildExpressionTree(String postfix) {
        Deque<Node> stack = new ArrayDeque<>();
        for (String token : postfix.split(" ")) {
            if (OPERATORS.contains(token)) {
                Node right = stack.pop();
                Node left = stack.pop();
                stack.push(new Node(token, left, right));
            } else {
                stack.push(new Node(token));
            }
        }
        return stack.pop();
    }

    static String toInfix(Node node, int parentPrecedence) {
        if (node.left == null && node.right == null) {
            return node.value;
        }
        int myPrecedence = PRECEDENCE.get(node.value);
        String leftStr = toInfix(node.left, myPrecedence);
        String rightStr = toInfix(node.right, myPrecedence);
        String expression = leftStr + " " + node.value + " " + rightStr;
        return myPrecedence < parentPrecedence ? "(" + expression + ")" : expression;
    }

    public static void main(String[] args) {
        Node tree = buildExpressionTree("3 4 + 5 2 - *");
        System.out.println(toInfix(tree, 0)); // (3 + 4) * (5 - 2)
    }
}

AST Basics

An Abstract Syntax Tree (AST) is the same core idea generalized far beyond arithmetic. Instead of only +, -, *, and numbers, an AST node can represent an if statement, a function call, a loop, or a variable declaration — each with its own set of children (a condition and two branches, a function name and an argument list, and so on). A compiler or interpreter's very first structural step after tokenizing and parsing source code is to build exactly this kind of tree: a representation that keeps every piece of the program's structure explicit and inspectable, ready for the type-checking, optimization, and code-generation passes that follow. An expression tree is simply an AST restricted to arithmetic.

8. Complexity Analysis

                Time and space: With $n$ tokens in the postfix expression, building the tree does exactly $n$ push/pop-style operations and creates at most $n$ nodes, so building is $O(n)$ time and $O(n)$ space. Evaluating or traversing the finished tree visits each of its $n$ nodes exactly once, so both are also $O(n)$ time, with $O(n)$ space in the worst case for the recursion stack of a skewed tree (an operator chain like a b + c + d + ...).
            

9. Applications & Alternatives

Where the tree structure earns its keep

Calculators: parse an expression once into a tree, then re-evaluate it repeatedly as input variables change.
Compilers and interpreters: build an AST as the first structural representation of source code before type-checking, optimization, or code generation.
Symbolic differentiation and simplification engines: apply differentiation or algebraic rules directly to subtrees, something a flattened numeric stack cannot support.
Spreadsheet formula evaluation: parse each cell's formula into a tree so dependencies, re-evaluation on change, and cross-cell references can all be tracked structurally.

When the only goal is a single numeric answer and the expression will never be inspected again, the stack-based postfix evaluation from Part 7 is simpler and uses less memory. Reach for an expression tree whenever the expression itself — not just its value — needs to survive past one computation.

10. Exercises & Mastery

Easy

Given the postfix form of (6 + 2) / 4, build its expression tree and evaluate it.

Medium

Build an expression tree directly from a fully-parenthesized infix string such as ((3 + 4) * (5 - 2)), without converting to postfix first. Hint: a recursive-descent parser that matches an opening parenthesis, recursively parses the left operand, reads the operator, recursively parses the right operand, and matches the closing parenthesis will do it in one pass.

Hard

Implement symbolic differentiation: given an expression tree that uses only +, -, *, and a single variable x, produce the derivative expression tree with respect to x. Apply the sum, difference, and product rules recursively at each internal node, and use the constant/variable base cases at the leaves.

Mastery challenge: Extend the differentiation exercise to also handle / (quotient rule) and integer exponents of x (power rule), then feed the resulting derivative tree back through the infix-reconstruction code from Section 7 to print a human-readable derivative. Discuss why the result may need a simplification pass (removing + 0 and * 1 nodes) to stay readable.

Review rhythm: tomorrow, rebuild the postfix-to-tree and evaluation code from memory; next week, implement the infix-reconstruction rule and verify it against a second worked example you invent yourself; several weeks later, sketch how an if statement would look as an AST node and compare it to the expression tree's operator node.

11. Summary Cheat Sheet

An expression tree keeps a postfix expression's structure explicit: leaves are operands, internal nodes are operators.
Building from postfix mirrors stack-based evaluation exactly, but the stack holds tree nodes instead of numbers.
Evaluation is postorder recursion: evaluate left, evaluate right, apply the operator.
Inorder traversal with a precedence check reconstructs fully-parenthesized infix — something the stack-based approach cannot do.
An AST generalizes the same idea to full programming-language constructs; compilers build one as their first structural view of source code.
Building, evaluating, and traversing an expression tree with $n$ tokens are all $O(n)$ time and space.

Cookie Consent

Expression Trees: Build, Evaluate & Reconstruct Infix

Table of Contents

1. Introduction & Motivation

2. Prerequisites

3. A Concrete Example

Building the tree for (3 + 4) * (5 - 2)

4. Core Insight

5. Building an Expression Tree from Postfix

6. Evaluating an Expression Tree

7. Inorder Traversal to Recover Infix

AST Basics

8. Complexity Analysis

9. Applications & Alternatives

Where the tree structure earns its keep

10. Exercises & Mastery

Easy

Medium

Hard

11. Summary Cheat Sheet

Cookie Consent

Expression Trees: Build, Evaluate & Reconstruct Infix

Table of Contents

1. Introduction & Motivation

2. Prerequisites

3. A Concrete Example

Building the tree for (3 + 4) * (5 - 2)

4. Core Insight

5. Building an Expression Tree from Postfix

6. Evaluating an Expression Tree

7. Inorder Traversal to Recover Infix

AST Basics

8. Complexity Analysis

9. Applications & Alternatives

Where the tree structure earns its keep

10. Exercises & Mastery

Easy

Medium

Hard

11. Summary Cheat Sheet

Continue the DSA Curriculum

Data Structures & Algorithms Hub

Part 7: Stack

Part 9: Trees