Expression Tree - Programming and Data Structures - Computer Science Engineering

Table of Contents
1. Expression tree in data structure
2. Uses of expression trees
3. Constructing an expression tree from linear expressions
4. Stack-based implementation idea (summary)
5. Example input and resulting tree construction
6. Implementation details and sample programs
7. Traversal relationships and notation conversion
8. Complexity and storage
9. Practical notes, common pitfalls and tips
10. Conclusion
View more

Expression tree in data structure

An expression tree is a binary tree that represents arithmetic or logical expressions. In an expression tree each internal node represents an operator and each leaf node represents an operand. The tree structure encodes the order of evaluation: operators near the leaves are applied before operators near the root (subject to explicit precedence and associativity encoded when the tree is built).

Properties and key points

• Each internal node denotes an operator (for example +, -, *, /, ^).
• Each leaf node denotes an operand (for example variables, constants, or literals).
• The structure captures operator precedence and associativity so that evaluation order is explicit and unambiguous.
• Operators that appear deeper in the tree are applied earlier than operators nearer the root.
• Typical associativity: most arithmetic operators such as +, -, *, / are left-associative; exponentiation (^) is commonly right-associative. Associativity is encoded in how the tree is constructed.
• Expression trees can be produced from a parsed expression using syntax-directed or semantic rules; they are closely related to parse trees and annotated parse trees.
• In compiler design, expression trees are used in semantic analysis and for intermediate representations of expressions.
• Expression trees are frequently treated as immutable in compiler contexts: instead of mutating a tree, transformations produce a new tree (this simplifies reasoning and optimisation).
• Expression trees provide a convenient data structure to convert between infix, prefix and postfix (in-order, pre-order and post-order traversals respectively), to evaluate expressions, and to perform algebraic transformations.

Example

Consider the expression 7 + ((1 + 8) × 3). An expression tree for this expression has + as the root, 7 as the left child, and a subtree representing ((1 + 8) × 3) as the right child.

Recursive evaluation (conceptual algorithm)

The usual recursive evaluation of an expression tree computes values by a post-order traversal: evaluate left subtree, evaluate right subtree, then apply the operator at the node.

function evaluate(node) if node is null return 0 // or error for empty tree if node is a leaf return numeric_value(node) x = evaluate(node.left) y = evaluate(node.right) return apply_operator(node.operator, x, y)

For the example 7 + ((1 + 8) × 3) the recursive computation proceeds by computing (1 + 8) = 9, then 9 × 3 = 27, then 7 + 27 = 34.

Uses of expression trees

• Evaluation of arithmetic and logical expressions.
• Conversion between notations: an inorder traversal (with parentheses) yields the infix expression, a preorder traversal yields prefix, and a postorder traversal yields postfix.
• Semantic analysis in compilers: expression trees act as an intermediate representation for optimisations and code generation.
• Simplification and symbolic manipulation: algebraic transformations, common-subexpression elimination and constant folding operate on expression trees.
• Representing lambda expressions and other language-level constructs in memory for interpreters and compilers.
• Clarifying operator precedence and resolving associativity ambiguities of textual expressions.

Constructing an expression tree from linear expressions

From postfix (Reverse Polish) notation

Building an expression tree from a postfix expression is straightforward using a stack:

• Scan the postfix expression from left to right.
• If the scanned token is an operand, create a leaf node and push it on the stack.
• If the scanned token is an operator, pop two nodes from the stack; make them the operator node's right and left children (the first popped becomes the right child and the second popped becomes the left child); push the new operator node back on the stack.
• When the scan finishes, the stack contains a single node which is the root of the expression tree.

From prefix (Polish) notation

To build from prefix notation, scan from right to left and apply the same stack-based idea: push operands, and when an operator is encountered, pop two nodes to become its children and push the new operator node back.

From infix notation

Constructing an expression tree directly from infix requires handling precedence and associativity. A common method is to first convert infix to postfix (for example using the Shunting Yard algorithm) and then build the tree from the resulting postfix expression.

Stack-based implementation idea (summary)

• Use a stack of tree nodes.
• Scan tokens left-to-right (for postfix): push operands; for an operator, pop two nodes, create an operator node with those nodes as children, then push the operator node.
• Final stack top is the expression-tree root.

Example input and resulting tree construction

Given the postfix string "XYZ*+W/", the stack-based procedure produces a tree whose inorder traversal prints:

X + Y * Z / W

Implementation details and sample programs

The following implementations demonstrate construction of an expression tree from a postfix expression and printing the inorder traversal. Each program uses the stack push/pop operations and a node structure/class that stores an operator/operand and left/right pointers.

Implementation in C

// C program for expression tree implementation #include <stdio.h> #include <stdlib.h> struct node { char info; struct node* l; struct node* r; struct node* nxt; // used to implement stack as linked list }; struct node *head = NULL; struct node* newnode(char data) { struct node* node = (struct node*) malloc(sizeof(struct node)); node->info = data; node->l = NULL; node->r = NULL; node->nxt = NULL; return node; } void Inorder(struct node* node) { if (node == NULL) return; Inorder(node->l); printf("%c ", node->info); Inorder(node->r); } void push(struct node* x) { if (head == NULL) head = x; else { x->nxt = head; head = x; } } struct node* pop() { struct node* n = head; head = head->nxt; return n; } int main() { char t[] = { 'X', 'Y', 'Z', '*', '+', 'W', '/' }; int n = sizeof(t) / sizeof(t[0]); int i; struct node *p, *q, *s; for (i = 0; i < n;="" i++)="" {="" if="" (t[i]="=" '+'="" ||="" t[i]="=" '-'="" ||="" t[i]="=" '*'="" ||="" t[i]="=" '/'="" ||="" t[i]="=" '^')="" {="" s="newnode(t[i]);" p="pop();" q="pop();" s-="">l = q; s->r = p; push(s); } else { s = newnode(t[i]); push(s); } } printf("The Inorder Traversal of Expression Tree: "); Inorder(s); return 0; }

The output of the above program is:

X + Y * Z / W

Implementation in C++

// C++ program for expression tree #include <bits/stdc++.h> using namespace std; class node { public: char info; node* l; node* r; node* nxt; node(char c) { info = c; l = NULL; r = NULL; nxt = NULL; } }; class Stack { node* head = NULL; public: void push(node* x) { if (head == NULL) head = x; else { x->nxt = head; head = x; } } node* pop() { node* p = head; head = head->nxt; return p; } }; class tree { public: void inorder(node* x) { if (x == NULL) return; inorder(x->l); cout < x-="">info < "="" ";="" inorder(x-="">r); } }; int main() { string str = "XYZ*+W/"; Stack s; tree t; node *p, *q, *re; int n = str.length(); for (int i = 0; i < n; i++) { if (str[i] == '+' || str[i] == '-' || str[i] == '*' || str[i] == '/' || str[i] == '^') { re = new node(str[i]); p = s.pop(); q = s.pop(); re->l = q; re->r = p; s.push(re); } else { re = new node(str[i]); s.push(re); } } cout << "The Inorder Traversal of Expression Tree: "; t.inorder(re); return 0; }

The output of the above program is:

X + Y * Z / W

Implementation in Java

// Java program for expression tree import java.util.*; class Node { char info; Node l, r; public Node(char data) { this.info = data; l = null; r = null; } } public class Main { public static boolean isOperator(char ch) { return (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '^'); } public static Node Tree(String postfix) { Stack<Node> st = new Stack<Node>(); Node t1, t2, temp; for (int i = 0; i < postfix.length(); i++) { char ch = postfix.charAt(i); if (!isOperator(ch)) { temp = new Node(ch); st.push(temp); } else { temp = new Node(ch); t1 = st.pop(); t2 = st.pop(); temp.l = t2; temp.r = t1; st.push(temp); } } temp = st.pop(); return temp; } public static void inorder(Node parent) { if (parent == null) return; inorder(parent.l); System.out.print(parent.info + " "); inorder(parent.r); } public static void main(String[] args) { String postfix = "XYZ*+W/"; Node r = Tree(postfix); inorder(r); } }

The output of the above program is:

X + Y * Z / W

Traversal relationships and notation conversion

• Inorder traversal (with appropriate parentheses) reproduces the original infix expression.
• Preorder traversal yields the prefix (Polish) notation.
• Postorder traversal yields the postfix (Reverse Polish) notation.
• Tree-based conversion is reliable because the order of evaluation is explicit in the structure; no operator precedence rules are required once the tree is built.

Complexity and storage

• Construction from a postfix expression using the stack algorithm visits each token once; time complexity is O(n) where n is the number of tokens.
• Evaluation by a post-order traversal also runs in O(n) time.
• Space complexity is O(n) for the tree nodes and O(h) additional stack space for recursion during traversal, where h is the tree height. The explicit stack used during construction is O(n) in the worst case.

Practical notes, common pitfalls and tips

• When building from postfix, be careful about the order in which nodes are popped and assigned as left and right children: the first popped node becomes the right subtree, the second popped node becomes the left subtree.
• Ensure the input expression tokens are correctly separated or tokenised (multi-digit numbers, identifiers and whitespace must be handled in real implementations).
• If converting from infix, prefer converting to postfix first (Shunting Yard algorithm) to simplify tree construction.
• Remember operator associativity rules when converting infix to postfix: for right-associative operators (for example exponentiation), the order of handling equal-precedence operators differs from left-associative ones.
• For compiler intermediate representations, expression trees may be annotated with types and other semantic attributes; these annotations are part of the annotated parse tree or the semantic rules used during construction.

Conclusion

Expression trees are a compact and clear representation of expressions that make evaluation, notation conversion and programmatic transformations straightforward. They are a standard tool in compilers, interpreters and symbolic-manipulation systems. Understanding how to build an expression tree from postfix/prefix/infix forms and how to traverse and evaluate it is essential in data structures, compiler construction and related areas of computer science.