Table of contents
1.
Introduction
2.
What is an Expression Tree in Data Structure?
3.
Use of Expression tree in Data Structure
4.
Evaluation of an Expression Tree
4.1.
Algorithm
5.
Implementation of Expression Tree in C++
5.1.
C++
6.
Main Functions of the Stack in Expression Tree Implementation
6.1.
Push:
6.2.
Pop:
6.3.
Peek (Top):
6.4.
Is Empty:
6.5.
Size:
7.
Generation of Expression Tree
8.
Implementation of Expression Tree
8.1.
Algorithm
8.2.
Implementation of Expression Tree in Java Programming Language
8.3.
Java
9.
Expression from Expression Tree
10.
Frequently Asked Questions
10.1.
What is an expression tree in data structure?
10.2.
What is the use of an expression tree?
10.3.
What is the difference between an expression tree and a binary tree?
10.4.
How to create an expression tree in C?
11.
Conclusion
Last Updated: Sep 24, 2024
Medium

Expression Tree in Data Structure

Author Harsh
1 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

An expression tree in data structures represents an expression using a tree format. After creating the expression tree, we can perform an inorder traversal to generate infix expressions. Likewise, conducting a postorder traversal on the expression tree produces postfix expressions.

Expression Tree in Data Structure

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:

Example Image of Expression tree in Data Structure

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

  1. Let exprTree be the input expression tree.
     
  2. Create a recursive function dfsTree(Node* node) to perform the dfs of the expression tree. Here Node represents individual nodes of the tree.
     
  3. If the node is null or the node represents an operand, return the node’s value.
     
  4. Otherwise, perform dfsTree(node->left) and dfsTree(node->right) and store them in L1 and L2.
     
  5. Finally, perform the operation represented by node->value between L1 and L2.

Implementation of Expression Tree in C++

Implementation of Expression Tree in  C

An expression tree is a binary tree used to represent arithmetic expressions. Each leaf node represents an operand (like a number), and each internal node represents an operator (like +, -, *, /).

  • C++

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;
}
You can also try this code with Online C++ Compiler
Run Code

 

Output

Value of the expression: 125

Main Functions of the Stack in Expression Tree Implementation

Push:

  • Function: This operation adds an element (usually a node) to the top of the stack.
  • Explanation: When building an expression tree, nodes representing operands (like numbers or variables) are pushed onto the stack. This helps keep track of the nodes as they are created and organized.

Pop:

  • Function: This operation removes and returns the top element from the stack.
  • Explanation: When an operator is encountered while processing an expression, nodes representing the operands must be popped from the stack to become children of the operator node. This is essential for correctly forming the tree structure, as operators need their respective operands to perform operations.

Peek (Top):

  • Function: This operation allows you to view the top element of the stack without removing it.
  • Explanation: Peek is often used to check the last node added to the stack to decide the next operation or determine the precedence of operators. It is helpful in maintaining the order of operations when constructing the tree.

Is Empty:

  • Function: This operation checks if the stack is empty.
  • Explanation: Before popping elements from the stack, it's essential to check whether the stack is empty to avoid underflow errors. This ensures that there are enough operands available for the operation being performed.

Size:

  • Function: This operation returns the current number of elements in the stack.
  • Explanation: Knowing the size of the stack can help in debugging and understanding how many nodes are currently being managed during the tree construction process. It can also be useful in managing memory and ensuring that the stack does not exceed its allocated space.

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.
Generation of Expression Tree
  • Now solve the left and right subtree similarly.
Generation of Expression Tree
Generation of Expression Tree

 

  • After solving the right and left subtree our final expression tree would become like the image given below:
Generation of Expression Tree

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

  1. Scan the expression from left to right.
     
  2. If an operand is found. Then create a node for this operand and push it into the stack.
     
  3. 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.
     
  4. Keep repeating the above two steps until we reach the end of our postfix expression.
     
  5. The node that is left behind in the stack represents the head of the expression tree.

Implementation of Expression Tree in Java Programming Language

  • Java

Java

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("");
 }
}
You can also try this code with Online Java Compiler
Run Code

 

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.

Expression from Expression Tree

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.

Check out this problem - Diameter Of Binary Tree

Also read - Data Structure MCQ

Frequently Asked Questions

What is an expression tree in data structure?

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, 

Recommended Readings:

You can also consider our Online Coding Courses such as the DSA in PythonC++ DSA CourseDSA in Java Course to give your career an edge over others.

Live masterclass