Expression Tree in Data Structure: Properties, Construction with Examples

Expression trees are a primary data structure for representing arithmetic and logical expressions in many notations (infix, postfix, and prefix). Expression trees can represent many kinds of expressions, depending on the operators, operands, and relationships based on the arrangement of the tree. Outlined below are the kinds of expressions that can be represented by expression trees:

1. Arithmetic Expressions

Arithmetic expressions use mathematical operations like addition, subtraction, multiplication, and division and are typically based on numerical values (whether constants or variables).

Expression Tree for 3 + 4 * 2

• Infix: 3 + 4 * 2
• Postfix: 3 4 2 * +
• Prefix: + 3 * 4 2

       +
      / \
     3   *
        / \
       4   2

In this example:

• The root is represented by the plus operator.
• The left child is operand 3.
• In this case, the operands are 4 and 2, and the right child is the multiplication operator (*).

2. Boolean Expressions

Boolean expressions represent logical operations such as AND, OR, NOT, and combinations of these operations. They refer to Boolean variables or constants (true and false).

Expression Tree for A AND B OR C

• Infix: A AND B OR C
• Postfix: A B AND C OR
• Prefix: OR AND A B C

        OR
       /  \
    AND    C
   /  \
  A    B

In this case:

• The root is the OR operator. 
• The left child is an AND operation, with A and B as operands. 
• The right child is operand C. 

3. Relational Expressions

Relational expressions compare two values and are used commonly in conditional expressions based upon relational operators—comparative expressions—like: =, >, <, >=, <=, and !=.

Expression Tree for A > B AND C < D:

• Infix: A > B AND C < D
• Postfix: A B > C D < AND
• Prefix: AND > A B < C D

        AND
       /    \
      >      <
     / \    / \
    A   B   C  D

Here:

• The root is the AND operator.
• The left child is a comparison (>) with operands A and B.
• The right child is a comparison (<) with operands C and D.

4. Conditional Expressions

Conditional expressions are expressions that can be used in a decision-making context, such as in if-else statements or a ternary operator. A common example is the ternary conditional operator (? :)

Expression Tree for x > 10 ? y : z:

• Infix: x > 10 ? y : z
• Postfix: x 10 > y z ? :
• Prefix: ? > x 10 y z

        ?
       /  \
      >    :
    / \   / \
   x  10  y  z

In this case:

• The root is the ternary conditional operator (?).
• The left child is the relational expression x > 10.
• The right child is the conditional operation (:), which accepts operands y and z.

An expression tree can be constructed using infix, prefix, or postfix notations. Let's explain how they are constructed and displayed referring to an example:

       +
      / \
     A   *
        / \
       B   C

Infix Notation

In infix notation, operators are placed between operands. This is the most common way of writing arithmetic expressions.

Construction Process (Infix to Expression Tree)

Step 1: Start with the lowest precedence operator (if multiple operators are present).

Step 2: Make this operator the root of the tree.

Step 3: The left subtree is created from the part of the expression to the left of the operator, and the right subtree is created from the part of the expression to the right of the operator.

Step 4: Recursively apply this process to the left and right subexpressions.

Example: A + B * C

• The  + has a lower precedence than *, so + becomes the root.
• Operand A becomes the left child of +.
• The expression B*C becomes the right subtree. Since * has the highest precedence, it is the root of this subtree, and B and C are its children.

Postfix Notation

In postfix notation, operators are placed after their operands.

Construction Process (Postfix to Expression Tree)

Step 1: Start from the left of the postfix expression and push operands onto a stack.

Step 2: When an operator is encountered, pop the required number of operands (2 for binary operators) from the stack, create a new node for the operator, and make the popped operands its children.

Step 3: Push the new operator node back onto the stack.

Step 4: At the end of the expression, the stack will contain a single node, which is the root of the expression tree.

Example: A B C * +

• Push A, B, and C to the stack.
• Pop B and C, form a node with *, and push it back to the stack.
• Pop A and the * nodes, then add a node with + and push it back into the stack.
• The final stack holds the tree's root.

Prefix Notation

Prefix notation consists of operators coming before their operands.

Construction Process (Prefix to Expression Tree)

Step 1: Start from the right of the prefix expression and push operands onto a stack.

Step 2: When an operator is encountered, pop the required number of operands (2 for binary operators) from the stack, create a new node for the operator, and make the popped operands its children.

Step 3: Push the new operator node back onto the stack.

Step 4: At the end of the expression, the stack will contain a single node, which is the root of the expression tree.

Example: + A * B C

• Push the A, B, and C elements onto the stack.
• Pop the B and C elements off, and make a node containing *, and push that back onto the stack.
• Pop the A element and the * node, make a node containing + and push that back onto the stack.
• The final stack will contain the root of the tree. 

Example	Notation	Example	Expression Tree
	Infix	A + B * C	+ (root), with left child A and right child * (subtree with B and C as leaves)
	Postfix	A B C * +	Same as the infix tree, but the construction order follows postfix operations
	Prefix	+ A * B C	Same as the infix tree, but the construction order follows prefix operations

Here are the advantages and disadvantages of the expression tree:

Advantages

• Expression trees can help to evaluate expressions easily and reliably by methodically applying operators in a structure.
• Expression trees can help condense complex expressions by re-arranging the tree structure.
• Expression trees can also be used for syntax checking (nothing to do with runtime errors that will be highlighted) in compilers - checking for correct grammer of an expression.
• Expression trees are used in many compilers with the goals of optimization through the implementation of algorithms, such as constant folding or common subexpression elimination.

Disadvantages

• The memory footprint of an expression tree can be very large - especially when the expression is very complex.
• Building the expression tree from the expression requires that an expression is parsed which can be time consuming.
• For a simple expression, a tree can be overkill, and direct evaluation may be more efficient.
• With various types of operator, such as unary or ternary, expression trees can be a bit harder to build actually. 

Here are some popular algorithms that can be used to manipulate and evaluate expression trees:

• Post-order Traversal: This traversal strategy is a depth-first traversal algorithm, to evaluate the expression trees by traversing the left and right lower trees before evaluating the operator at that node.
• Pre-order Traversal: This is sometimes used in expression trees if we want to traverse the entire tree or convert it to prefix expression form. 
• In-order Traversal: When we print operands between operators we are representing an infix expression.

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

// Define a structure for the tree node
struct Node {
    char data;
    struct Node *left, *right;
};

// Stack structure to hold nodes during tree construction
struct Stack {
    int top;
    unsigned capacity;
    struct Node **array;
};
// Function to create a new tree node
struct Node* newNode(char data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = node->right = NULL;
    return node;
}

// Function to create a stack for nodes
struct Stack* createStack(unsigned capacity) {
    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
    stack->capacity = capacity;
    stack->top = -1;
    stack->array = (struct Node**)malloc(stack->capacity * sizeof(struct Node*));
    return stack;
}

// Stack operations
int isFull(struct Stack* stack) { return stack->top == stack->capacity - 1; }
int isEmpty(struct Stack* stack) { return stack->top == -1; }
void push(struct Stack* stack, struct Node* node) {
    if (isFull(stack)) return;
    stack->array[++stack->top] = node;
}
struct Node* pop(struct Stack* stack) {
    if (isEmpty(stack)) return NULL;
    return stack->array[stack->top--];
}

// Function to check if a character is an operator
int isOperator(char c) {
    return (c == '+' || c == '-' || c == '*' || c == '/');
}

// Function to build the expression tree from a postfix expression
struct Node* constructExpressionTree(char* postfix) {
    struct Stack* stack = createStack(strlen(postfix));
    struct Node *node, *left, *right;
    
    for (int i = 0; postfix[i]; i++) {
        // If the character is an operand, create a node and push to stack
        if (!isOperator(postfix[i])) {
            node = newNode(postfix[i]);
            push(stack, node);
        } else {
            // If the character is an operator, pop two nodes and make them children
            right = pop(stack);
            left = pop(stack);
            node = newNode(postfix[i]);
            node->left = left;
            node->right = right;
            push(stack, node);
        }
    }
    
    return pop(stack); // The final node will be the root of the tree
}

// Function to perform inorder traversal (infix notation)
void inorder(struct Node* root) {
    if (root) {
        inorder(root->left);
        printf("%c ", root->data);
        inorder(root->right);
    }
}

// Function to perform preorder traversal (prefix notation)
void preorder(struct Node* root) {
    if (root) {
        printf("%c ", root->data);
        preorder(root->left);
        preorder(root->right);
    }
}

// Function to perform postorder traversal (postfix notation)
void postorder(struct Node* root) {
    if (root) {
        postorder(root->left);
        postorder(root->right);
        printf("%c ", root->data);
    }
}

// Main function
int main() {
    char postfix[] = "ab+c*d-";  // Example postfix expression: (a + b) * c - d
    struct Node* root = constructExpressionTree(postfix);
    
    printf("Infix Expression: ");
    inorder(root);
    printf("\n");
    
    printf("Prefix Expression: ");
    preorder(root);
    printf("\n");
    
    printf("Postfix Expression: ");
    postorder(root);
    printf("\n");

    return 0;
}

Output

Infix Expression: a + b * c - d 
Prefix Expression: - * + a b c d 
Postfix Expression: a b + c * d -

To summarize, an expression tree is a binary tree that represents mathematical expressions in which the leaf nodes are operands and the interior nodes are operators. Expression trees allow for evaluation of an expression while preserving the precedence of operators and for transformations to be simplified. Expression trees are often used in both compilers and calculators in the computer algebra systems for parsing, evaluating or optimizing expressions. Using post-order traversal, arbitrary expressions can be evaluated or simplified quickly.

1. Can an expression tree be utilized to perform symbolic computations?

Yes, expression trees are an important component of symbolic computation systems, allowing for symbolic manipulation and simplification of algebraic expressions.

2. What is the time complexity for evaluating an expression tree?

The time complexity for evaluating an expression tree is O(n), where means the total number of nodes. This is because a post-order traversal processes each node exactly once.