An expression tree in Data structure is used to represent an expression in the form of a tree. After generating the expression tree of an expression, we can perform inorder traversal to generate infix expressions. Similarly, doing a postorder traversal of the expression tree will generate postfix expressions.

In this blog, we are going to discuss the expression tree in data structure and how we can generate an expression tree from a given expression using stacks.

So, let’s get started.

What is an Expression Tree in Data Structure?

Expression trees are used to express a mathematical expression in the form of a binary tree. Expression trees are binary trees in which each internal (non-leaf) node is an operator and each leaf node is an operand.

First, let us discuss how to evaluate a given expression tree in data structure. For example, if we have an expression A * B + C / D. Then, the expression tree would be like the image given below:

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Use of Expression tree in Data Structure

Expression trees are used to evaluate mathematical expressions by traversing the tree in a specific order (such as in-order, post-order or pre-order). This approach allows the tree to be evaluated recursively and efficiently. Additionally, an expression tree can be used to convert the expressions from infix notation to postfix or prefix notation and vice versa.

Expression trees are also used in compilers and interpreters to represent the syntax tree of a program. This allows for easy manipulation and evaluation of the program's structure and logic.

Expression trees are also used in computer algebra systems and symbolic computation software to manipulate algebraic expressions by simplification, differentiation, and integration.

Evaluation of an Expression Tree

We can evaluate an expression tree in Data Structure using a simple Depth First Traversal. Let us discuss its implementation using the same expression tree described above with A = 10, B = 12, C = 25 and D = 5.

Algorithm

Let exprTree be the input expression tree.

Create a recursive function dfsTree(Node* node) to perform the dfs of the expression tree. Here Node represents individual nodes of the tree.

If the node is null or the node represents an operand, return the node’s value.

Otherwise, perform dfsTree(node->left) and dfsTree(node->right) and store them in L1 and L2.

Finally, perform the operation represented by node->value between L1 and L2.

Implementation of Expression Tree in C++

#include<bits/stdc++.h>
using namespace std;
// Node of the tree
class Node
{
public:
int operand, isOperand;
char opr;
Node *left, *right;
};
// Create a node of the tree
Node *createNode(int operand, char opr, int isOperand)
{
Node *node = new Node();
node->isOperand = isOperand;
if(isOperand) {
node->operand = operand;
}
else node->opr = opr;
node->left = NULL;
node->right = NULL;
return node;
}
// Doing a dfs
Node* dfsTree(Node* node) {
// Cases mentioned in the algorithm
if(node == NULL) {
return NULL;
}
if(node->isOperand) {
return node;
}
// Solve for left and right
Node* solveLeft = dfsTree(node->left);
Node* solveRight = dfsTree(node->right);
// Perform operation represented by this node
int l1 = solveLeft->operand; int l2 = solveRight->operand;
int val;
if(node->opr == '/') {
val = l1/l2;
}
else if(node->opr == '*') {
val = l1 * l2;
}
else if(node->opr == '+') {
val = l1 + l2;
}
else if(node->opr == '-') {
val = l1 - l2;
}
// Return the new node
Node* newNode = createNode(val, '#', 1);
return newNode;
}
int main()
{
// Create the expression tree
Node *newNode;
Node *head = createNode(-1, '+', 0);
newNode = createNode(-1, '*', 0);
head->left = newNode;
newNode = createNode(-1, '/', 0);
head->right = newNode;
newNode = createNode(10, '#', 1);
head->left->left = newNode;
newNode = createNode(12, '#', 1);
head->left->right = newNode;
newNode = createNode(25, '#', 1);
head->right->left = newNode;
newNode = createNode(5, '#', 1);
head->right->right = newNode;
Node* ans = dfsTree(head);
cout<<"Value of the expression: "<<ans->operand<<endl;
}

Output

Value of the expression: 125

Generation of Expression Tree

Let’s understand the process of generation of an expression tree intuitively using the expression tree described in the previous section.

Expression: A * B + C / D

Scan the expression and according to the associativity and precedence find the operator which will be evaluated at last.

In our example, the + operator will be evaluated in the last so keep it as the root node and divide the remaining expression into left and right subtrees.

Now solve the left and right subtree similarly.

After solving the right and left subtree our final expression tree would become like the image given below:

Implementation of Expression Tree

Till now we have seen how we generate expression trees in general. But how do we write the code to generate the expression tree in data structure?

In this section, we will discuss how we can write the code to generate the expression tree from a postfix expression.

Algorithm

Scan the expression from left to right.

If an operand is found. Then create a node for this operand and push it into the stack.

If an operator is found. Pop two nodes from the stack and make a node keeping the operator as the root node and the two items as the left and the right child. Push the newly generated node into the stack.

Keep repeating the above two steps until we reach the end of our postfix expression.

The node that is left behind in the stack represents the head of the expression tree.

Implementation of Expression Tree in Java Programming Language

import java.util.Stack;
// represents a node in our expression tree
class Node {
char data;
Node left;
Node right;
// constructor
public Node(char data) {
this.data = data;
left = right = null;
}
}
// main class
public class ExpressionTree {
// return true if the ch is an operator
public static boolean isOperator(char ch) {
return (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '^');
}
// generate expression tree and return the root node
public static Node genExpTree(String postfix) {
// stack to hold character
Stack<Node> st = new Stack<Node>();
// to create a temp node with l and r as left and right subtree
Node l, r, temp;
// traversing the postfix expression
for (int i = 0; i < postfix.length(); i++) {
// a character is found
// push it into the stack
if (!isOperator(postfix.charAt(i))) {
temp = new Node(postfix.charAt(i));
st.push(temp);
} else {
// creating new temp node
temp = new Node(postfix.charAt(i));
// getting two items from our stack
l = st.pop();
r = st.pop();
// attaching the above two items as the left and right child of our
// temp node
temp.left = r;
temp.right = l;
// pushing the temp node into our stack
st.push(temp);
}
}
// getting the root node
temp = st.pop();
// returning the root node
return temp;
}
// print the inorder traversal of tree
public static void inorder(Node root) {
// return if root is null
if (root == null) return;
// inorder traversal
inorder(root.left);
System.out.print(root.data);
inorder(root.right);
}
// main function
public static void main(String[] args) {
// postfix expression
String expression = "AB*CD/+";
// calling our algorithm
Node root = genExpTree(expression);
System.out.print("Inorder Expression: ");
// printing the expression tree inorder
inorder(root);
System.out.println("");
}
}

Output

Inorder Expression: A*B+C/D

Expression from Expression Tree

After constructing the expression tree we can convert the given expression into Pre, post, and inorder by just traversing the tree. For example, if we want to get the prefix expression of the above expression we can do the preorder traversal of the expression tree and the result that we’ll get will be the prefix expression of the expression.

As we can see in the above image the preorder, inorder, and postorder of the expression tree is also the prefix, infix, and postfix of the same expression respectively.

An expression tree represents mathematical expressions arranged in a tree-like data structure. In other words, it is a tree with non-leaf nodes as operators and leaf nodes as operands.

What is the use of an expression tree?

The primary goal of using expression trees is to make complex expressions easy to evaluate and represent. Other than this, the tree can be traversed in various ways, such as pre, post or inorder traversals giving different information about the expression.

What is the difference between an expression tree and a binary tree?

An expression tree is used to represent mathematical expressions in a tree-like structure. It organizes operands and operators in a way that reflects the expression's evaluation order, whereas A binary tree is a tree data structure where each node has at most two child nodes, usually referred to as the left child and the right child. It's used for various purposes, including organizing data and facilitating efficient searching.

How to create an expression tree in C?

To create an expression tree in C, you can use a recursive function that takes in the expression as a string and creates the tree by breaking it down into smaller expressions and creating nodes for the operators and operands.

Conclusion

In this article, we have extensively discussed the expression tree in data structure. We have also seen how we can generate the expression tree from a given expression. And how we can get prefix, postfix, and infix expressions from a given expression tree.

If you think this blog has helped you enhance your knowledge about Expression tree in data structure and if you would like to learn more. check out our articles,