Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
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
4.2.
Implementation of Expression Tree in C++
5.
Generation of Expression Tree
6.
Implementation of Expression Tree
6.1.
Algorithm
6.2.
Implementation of Expression Tree in Java Programming Language
7.
Expression from Expression Tree
8.
Frequently Asked Questions
8.1.
What is an expression tree in data structure?
8.2.
What is the use of an expression tree?
8.3.
What is the difference between an expression tree and a binary tree?
8.4.
How to create an expression tree in C?
9.
Conclusion
Last Updated: Mar 27, 2024
Medium

Expression Tree in Data Structure

Author Harsh
1 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction

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.

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
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

  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++

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

 

  • After solving the right and left subtree our final expression tree would become like the image given below:
final 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

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.

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.

Do upvote our blog to help other ninjas grow. 

Happy Learning, Ninja!🥷✨

Previous article
Clone a Binary Tree with Random Pointers
Next article
Deletion in Threaded Binary Search Tree
Live masterclass