Infix, Postfix and Prefix Expressions/Notations
Mathematical formulas often involve complex expressions that require a clear understanding of the order of operations. To represent these expressions, we use different notations, each with its own advantages and disadvantages. In this article, we will explore three common expression notations: infix, prefix, and postfix.
Infix Expressions
Infix expressions are mathematical expressions where the operator is placed between its operands. This is the most common mathematical notation used by humans. For example, the expression “2 + 3” is an infix expression, where the operator “+” is placed between the operands “2” and “3”.
Infix notation is easy to read and understand for humans, but it can be difficult for computers to evaluate efficiently. This is because the order of operations must be taken into account, and parentheses can be used to override the default order of operations.
Common way of writing Infix expressions:
- Infix notation is the notation that we are most familiar with. For example, the expression “2 + 3” is written in infix notation.
- In infix notation, operators are placed between the operands they operate on. For example, in the expression “2 + 3”, the addition operator “+” is placed between the operands “2” and “3”.
- Parentheses are used in infix notation to specify the order in which operations should be performed. For example, in the expression “(2 + 3) * 4”, the parentheses indicate that the addition operation should be performed before the multiplication operation.
Operator precedence rules:
Infix expressions follow operator precedence rules, which determine the order in which operators are evaluated. For example, multiplication and division have higher precedence than addition and subtraction. This means that in the expression “2 + 3 * 4”, the multiplication operation will be performed before the addition operation.
Here’s the table summarizing the operator precedence rules for common mathematical operators:
| Operator |
Precedence |
| Parentheses () |
Highest |
| Exponents ^ |
High |
| Multiplication * |
Medium |
| Division / |
Medium |
| Addition + |
Low |
| Subtraction – |
Low |
Evaluating Infix Expressions
Evaluating infix expressions requires additional processing to handle the order of operations and parentheses. First convert the infix expression to postfix notation. This can be done using a stack or a recursive algorithm. Then evaluate the postfix expression.
Advantages of Infix Expressions
- More natural and easier to read and understand for humans.
- Widely used and supported by most programming languages and calculators.
Disadvantages Infix Expressions
- Requires parentheses to specify the order of operations.
- Can be difficult to parse and evaluate efficiently.
Prefix Expressions (Polish Notation)
Prefix expressions are also known as Polish notation, are a mathematical notation where the operator precedes its operands. This differs from the more common infix notation, where the operator is placed between its operands.
In prefix notation, the operator is written first, followed by its operands. For example, the infix expression “a + b” would be written as “+ a b” in prefix notation.
Evaluating prefix expressions can be useful in certain scenarios, such as when dealing with expressions that have a large number of nested parentheses or when using a stack-based programming language.
Advantages of Prefix Expressions
- No need for parentheses, as the operator always precedes its operands.
- Easier to parse and evaluate using a stack-based algorithm.
- Can be more efficient in certain situations, such as when dealing with expressions that have a large number of nested parentheses.
Disadvantages of Prefix Expressions
- Can be difficult to read and understand for humans.
- Not as commonly used as infix notation.
Postfix Expressions (Reverse Polish Notation)
Postfix expressions are also known as Reverse Polish Notation (RPN), are a mathematical notation where the operator follows its operands. This differs from the more common infix notation, where the operator is placed between its operands.
In postfix notation, operands are written first, followed by the operator. For example, the infix expression “5 + 2” would be written as “5 2 +” in postfix notation.
Evaluating postfix expressions can be useful in certain scenarios, such as when dealing with expressions that have a large number of nested parentheses or when using a stack-based programming language.
Advantages of Postfix Notation
- Also eliminates the need for parentheses.
- Easier to read and understand for humans.
- More commonly used than prefix notation.
Disadvantages of Postfix Expressions
- Requires a stack-based algorithm for evaluation.
- Can be less efficient than prefix notation in certain situations.
Comparison of Infix, Prefix and Postfix Expressions
Let’s compare infix, prefix, and postfix notations across various criteria:
| spect |
Infix Notation |
Prefix Notation (Polish Notation) |
Postfix Notation (Reverse Polish Notation) |
| Readability |
Human-readable |
Less human-readable, requires familiarity |
Less human-readable, requires familiarity |
| Operator Placement |
Between operands |
Before operands |
After operands |
| Parentheses Requirement |
Often required |
Not required |
Not required |
| Operator Precedence Tracking |
Required, parentheses determine precedence |
Not required, operators have fixed precedence |
Not required, operators have fixed precedence |
| Evaluation Method |
Left-to-right |
Right-to-left |
Left-to-right |
| Ambiguity Handling |
May require explicit use of parentheses |
Ambiguity rare, straightforward evaluation |
Ambiguity rare, straightforward evaluation |
| Unary Operator Handling |
Requires careful placement |
Simplified handling due to explicit notation |
Simplified handling due to explicit notation |
| Computer Efficiency |
Less efficient due to precedence tracking and parentheses handling |
More efficient due to fixed precedence and absence of parentheses |
More efficient due to fixed precedence and absence of parentheses |
| Usage |
Common in everyday arithmetic and mathematical notation |
Common in computer science and programming languages |
Common in computer science and programming languages |
Frequently Asked Questions on Infix, Postfix and Prefix Expressions
1. What is an infix expression?
An infix expression is a mathematical expression in which the operators are placed between the operands.
2. What is a postfix expression?
A postfix expression is a mathematical expression in which the operators are placed after the operands.
3. What is a prefix expression?
A prefix expression is a mathematical expression in which the operators are placed before the operands.
4. How are infix expressions evaluated?
Infix expressions are evaluated by following the rules of operator precedence and using parentheses to specify the order of operations.
5. How are postfix expressions evaluated?
Postfix expressions are evaluated by scanning the expression from left to right and using a stack to keep track of operands and operators.
6. How are prefix expressions evaluated?
Prefix expressions are evaluated by scanning the expression from right to left and using a stack to keep track of operands and operators.
7. What are the advantages of postfix and prefix expressions over infix expressions?
Postfix and prefix expressions eliminate the need for parentheses to specify the order of operations and make it easier to evaluate expressions using algorithms.
8. Can infix expressions be converted to postfix or prefix expressions?
Yes, infix expressions can be converted to postfix or prefix expressions using algorithms such as the shunting yard algorithm for postfix conversion and the reverse polish notation for prefix conversion.
9. Are postfix and prefix expressions more efficient than infix expressions in terms of evaluation?
Postfix and prefix expressions are more efficient for evaluation as they are easier to parse and evaluate using algorithms that do not require parentheses or multiple passes through the expression.
10. When should I use infix, postfix, or prefix expressions in my programming code?
Infix expressions are commonly used for human readability, while postfix and prefix expressions are preferred for efficient evaluation in programming languages and mathematical computations.
Related Articles:
------
Convert Infix expression to Postfix expression
Write a program to convert an Infix expression to Postfix form.
Infix expression: The expression of the form “a operator b” (a + b) i.e., when an operator is in-between every pair of operands.
Postfix expression: The expression of the form “a b operator” (ab+) i.e., When every pair of operands is followed by an operator.
Examples:
Input: A + B * C + D
Output: ABC*+D+
Input: ((A + B) – C * (D / E)) + F
Output: AB+CDE/*-F+
Why postfix representation of the expression?
The compiler scans the expression either from left to right or from right to left.
Consider the expression: a + b * c + d
- The compiler first scans the expression to evaluate the expression b * c, then again scans the expression to add a to it.
- The result is then added to d after another scan.
The repeated scanning makes it very inefficient. Infix expressions are easily readable and solvable by humans whereas the computer cannot differentiate the operators and parenthesis easily so, it is better to convert the expression to postfix(or prefix) form before evaluation.
The corresponding expression in postfix form is abc*+d+. The postfix expressions can be evaluated easily using a stack.
How to convert an Infix expression to a Postfix expression?
To convert infix expression to postfix expression, use the stack data structure. Scan the infix expression from left to right. Whenever we get an operand, add it to the postfix expression and if we get an operator or parenthesis add it to the stack by maintaining their precedence.
Below are the steps to implement the above idea:
- Scan the infix expression from left to right.
- If the scanned character is an operand, put it in the postfix expression.
- Otherwise, do the following
- If the precedence and associativity of the scanned operator are greater than the precedence and associativity of the operator in the stack [or the stack is empty or the stack contains a ‘(‘ ], then push it in the stack. [‘^‘ operator is right associative and other operators like ‘+‘,’–‘,’*‘ and ‘/‘ are left-associative].
- Check especially for a condition when the operator at the top of the stack and the scanned operator both are ‘^‘. In this condition, the precedence of the scanned operator is higher due to its right associativity. So it will be pushed into the operator stack.
- In all the other cases when the top of the operator stack is the same as the scanned operator, then pop the operator from the stack because of left associativity due to which the scanned operator has less precedence.
- Else, Pop all the operators from the stack which are greater than or equal to in precedence than that of the scanned operator.
- After doing that Push the scanned operator to the stack. (If you encounter parenthesis while popping then stop there and push the scanned operator in the stack.)
- If the scanned character is a ‘(‘, push it to the stack.
- If the scanned character is a ‘)’, pop the stack and output it until a ‘(‘ is encountered, and discard both the parenthesis.
- Repeat steps 2-5 until the infix expression is scanned.
- Once the scanning is over, Pop the stack and add the operators in the postfix expression until it is not empty.
- Finally, print the postfix expression.
Illustration:
Follow the below illustration for a better understanding
Consider the infix expression exp = “a+b*c+d”
and the infix expression is scanned using the iterator i, which is initialized as i = 0.
1st Step: Here i = 0 and exp[i] = ‘a’ i.e., an operand. So add this in the postfix expression. Therefore, postfix = “a”.
Add ‘a’ in the postfix
2nd Step: Here i = 1 and exp[i] = ‘+’ i.e., an operator. Push this into the stack. postfix = “a” and stack = {+}.
Push ‘+’ in the stack
3rd Step: Now i = 2 and exp[i] = ‘b’ i.e., an operand. So add this in the postfix expression. postfix = “ab” and stack = {+}.
Add ‘b’ in the postfix
4th Step: Now i = 3 and exp[i] = ‘*’ i.e., an operator. Push this into the stack. postfix = “ab” and stack = {+, *}.
Push ‘*’ in the stack
5th Step: Now i = 4 and exp[i] = ‘c’ i.e., an operand. Add this in the postfix expression. postfix = “abc” and stack = {+, *}.
Add ‘c’ in the postfix
6th Step: Now i = 5 and exp[i] = ‘+’ i.e., an operator. The topmost element of the stack has higher precedence. So pop until the stack becomes empty or the top element has less precedence. ‘*’ is popped and added in postfix. So postfix = “abc*” and stack = {+}.
Pop ‘*’ and add in postfix
Now top element is ‘+‘ that also doesn’t have less precedence. Pop it. postfix = “abc*+”.
Pop ‘+’ and add it in postfix
Now stack is empty. So push ‘+’ in the stack. stack = {+}.
Push ‘+’ in the stack
7th Step: Now i = 6 and exp[i] = ‘d’ i.e., an operand. Add this in the postfix expression. postfix = “abc*+d”.
Add ‘d’ in the postfix
Final Step: Now no element is left. So empty the stack and add it in the postfix expression. postfix = “abc*+d+”.
Pop ‘+’ and add it in postfix
Below is the implementation of the above algorithm:
C++14
#include <bits/stdc++.h>
using namespace std;
int prec(char c) {
if (c == '^')
return 3;
else if (c == '/' || c == '*')
return 2;
else if (c == '+' || c == '-')
return 1;
else
return -1;
}
char associativity(char c) {
if (c == '^')
return 'R';
return 'L';
}
void infixToPostfix(string s) {
stack<char> st;
string result;
for (int i = 0; i < s.length(); i++) {
char c = s[i];
if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9'))
result += c;
else if (c == '(')
st.push('(');
else if (c == ')') {
while (st.top() != '(') {
result += st.top();
st.pop();
}
st.pop();
}
else {
while (!st.empty() && prec(s[i]) < prec(st.top()) ||
!st.empty() && prec(s[i]) == prec(st.top()) &&
associativity(s[i]) == 'L') {
result += st.top();
st.pop();
}
st.push(c);
}
}
while (!st.empty()) {
result += st.top();
st.pop();
}
cout << result << endl;
}
int main() {
string exp = "a+b*(c^d-e)^(f+g*h)-i";
infixToPostfix(exp);
return 0;
}
|
C
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int prec(char c) {
if (c == '^')
return 3;
else if (c == '/' || c == '*')
return 2;
else if (c == '+' || c == '-')
return 1;
else
return -1;
}
char associativity(char c) {
if (c == '^')
return 'R';
return 'L';
}
void infixToPostfix(char s[]) {
char result[1000];
int resultIndex = 0;
int len = strlen(s);
char stack[1000];
int stackIndex = -1;
for (int i = 0; i < len; i++) {
char c = s[i];
if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9')) {
result[resultIndex++] = c;
}
else if (c == '(') {
stack[++stackIndex] = c;
}
else if (c == ')') {
while (stackIndex >= 0 && stack[stackIndex] != '(') {
result[resultIndex++] = stack[stackIndex--];
}
stackIndex--;
}
else {
while (stackIndex >= 0 && (prec(s[i]) < prec(stack[stackIndex]) ||
prec(s[i]) == prec(stack[stackIndex]) &&
associativity(s[i]) == 'L')) {
result[resultIndex++] = stack[stackIndex--];
}
stack[++stackIndex] = c;
}
}
while (stackIndex >= 0) {
result[resultIndex++] = stack[stackIndex--];
}
result[resultIndex] = '\0';
printf("%s\n", result);
}
int main() {
char exp[] = "a+b*(c^d-e)^(f+g*h)-i";
infixToPostfix(exp);
return 0;
}
|
Java
import java.util.Stack;
public class InfixToPostfix {
static int prec(char c) {
if (c == '^')
return 3;
else if (c == '/' || c == '*')
return 2;
else if (c == '+' || c == '-')
return 1;
else
return -1;
}
static char associativity(char c) {
if (c == '^')
return 'R';
return 'L';
}
static void infixToPostfix(String s) {
StringBuilder result = new StringBuilder();
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9')) {
result.append(c);
}
else if (c == '(') {
stack.push(c);
}
else if (c == ')') {
while (!stack.isEmpty() && stack.peek() != '(') {
result.append(stack.pop());
}
stack.pop();
}
else {
while (!stack.isEmpty() && (prec(s.charAt(i)) < prec(stack.peek()) ||
prec(s.charAt(i)) == prec(stack.peek()) &&
associativity(s.charAt(i)) == 'L')) {
result.append(stack.pop());
}
stack.push(c);
}
}
while (!stack.isEmpty()) {
result.append(stack.pop());
}
System.out.println(result);
}
public static void main(String[] args) {
String exp = "a+b*(c^d-e)^(f+g*h)-i";
infixToPostfix(exp);
}
}
|
Python3
def prec(c):
if c == '^':
return 3
elif c == '/' or c == '*':
return 2
elif c == '+' or c == '-':
return 1
else:
return -1
def associativity(c):
if c == '^':
return 'R'
return 'L'
def infix_to_postfix(s):
result = []
stack = []
for i in range(len(s)):
c = s[i]
if ('a' <= c <= 'z') or ('A' <= c <= 'Z') or ('0' <= c <= '9'):
result.append(c)
elif c == '(':
stack.append(c)
elif c == ')':
while stack and stack[-1] != '(':
result.append(stack.pop())
stack.pop()
else:
while stack and (prec(s[i]) < prec(stack[-1]) or
(prec(s[i]) == prec(stack[-1]) and associativity(s[i]) == 'L')):
result.append(stack.pop())
stack.append(c)
while stack:
result.append(stack.pop())
print(''.join(result))
exp = "a+b*(c^d-e)^(f+g*h)-i"
infix_to_postfix(exp)
|
C#
using System;
using System.Collections.Generic;
class Program
{
static int Prec(char c)
{
if (c == '^')
return 3;
else if (c == '/' || c == '*')
return 2;
else if (c == '+' || c == '-')
return 1;
else
return -1;
}
static char Associativity(char c)
{
if (c == '^')
return 'R';
return 'L';
}
static void InfixToPostfix(string s)
{
Stack<char> stack = new Stack<char>();
List<char> result = new List<char>();
for (int i = 0; i < s.Length; i++)
{
char c = s[i];
if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9'))
{
result.Add(c);
}
else if (c == '(')
{
stack.Push(c);
}
else if (c == ')')
{
while (stack.Count > 0 && stack.Peek() != '(')
{
result.Add(stack.Pop());
}
stack.Pop();
}
else
{
while (stack.Count > 0 && (Prec(s[i]) < Prec(stack.Peek()) ||
Prec(s[i]) == Prec(stack.Peek()) &&
Associativity(s[i]) == 'L'))
{
result.Add(stack.Pop());
}
stack.Push(c);
}
}
while (stack.Count > 0)
{
result.Add(stack.Pop());
}
Console.WriteLine(string.Join("", result));
}
static void Main()
{
string exp = "a+b*(c^d-e)^(f+g*h)-i";
InfixToPostfix(exp);
}
}
|
Javascript
function prec(c) {
if(c == '^')
return 3;
else if(c == '/' || c=='*')
return 2;
else if(c == '+' || c == '-')
return 1;
else
return -1;
}
function infixToPostfix(s) {
let st = [];
let result = "";
for(let i = 0; i < s.length; i++) {
let c = s[i];
if((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9'))
result += c;
else if(c == '(')
st.push('(');
else if(c == ')') {
while(st[st.length - 1] != '(')
{
result += st[st.length - 1];
st.pop();
}
st.pop();
}
else {
while(st.length != 0 && prec(s[i]) <= prec(st[st.length - 1])) {
result += st[st.length - 1];
st.pop();
}
st.push(c);
}
}
while(st.length != 0) {
result += st[st.length - 1];
st.pop();
}
document.write(result + "</br>");
}
let exp = "a+b*(c^d-e)^(f+g*h)-i";
infixToPostfix(exp);
|
Time Complexity: O(N), where N is the size of the infix expression
Auxiliary Space: O(N), where N is the size of the infix expression
------
Prefix to Infix Conversion
Infix : An expression is called the Infix expression if the operator appears in between the operands in the expression. Simply of the form (operand1 operator operand2).
Example : (A+B) * (C-D)
Prefix : An expression is called the prefix expression if the operator appears in the expression before the operands. Simply of the form (operator operand1 operand2).
Example : *+AB-CD (Infix : (A+B) * (C-D) )
Given a Prefix expression, convert it into a Infix expression.
Computers usually does the computation in either prefix or postfix (usually postfix). But for humans, its easier to understand an Infix expression rather than a prefix. Hence conversion is need for human understanding.
Examples:
Input : Prefix : *+AB-CD
Output : Infix : ((A+B)*(C-D))
Input : Prefix : *-A/BC-/AKL
Output : Infix : ((A-(B/C))*((A/K)-L))
Algorithm for Prefix to Infix:
- Read the Prefix expression in reverse order (from right to left)
- If the symbol is an operand, then push it onto the Stack
- If the symbol is an operator, then pop two operands from the Stack
Create a string by concatenating the two operands and the operator between them.
string = (operand1 + operator + operand2)
And push the resultant string back to Stack
- Repeat the above steps until the end of Prefix expression.
- At the end stack will have only 1 string i.e resultant string
Implementation:
C++
#include <iostream>
#include <stack>
using namespace std;
bool isOperator(char x) {
switch (x) {
case '+':
case '-':
case '/':
case '*':
case '^':
case '%':
return true;
}
return false;
}
string preToInfix(string pre_exp) {
stack<string> s;
int length = pre_exp.size();
for (int i = length - 1; i >= 0; i--) {
if (isOperator(pre_exp[i])) {
string op1 = s.top(); s.pop();
string op2 = s.top(); s.pop();
string temp = "(" + op1 + pre_exp[i] + op2 + ")";
s.push(temp);
}
else {
s.push(string(1, pre_exp[i]));
}
}
return s.top();
}
int main() {
string pre_exp = "*-A/BC-/AKL";
cout << "Infix : " << preToInfix(pre_exp);
return 0;
}
|
Java
import java.util.Stack;
class GFG{
static boolean isOperator(char x)
{
switch(x)
{
case '+':
case '-':
case '*':
case '/':
case '^':
case '%':
return true;
}
return false;
}
public static String convert(String str)
{
Stack<String> stack = new Stack<>();
int l = str.length();
for(int i = l - 1; i >= 0; i--)
{
char c = str.charAt(i);
if (isOperator(c))
{
String op1 = stack.pop();
String op2 = stack.pop();
String temp = "(" + op1 + c + op2 + ")";
stack.push(temp);
}
else
{
stack.push(c + "");
}
}
return stack.pop();
}
public static void main(String[] args)
{
String exp = "*-A/BC-/AKL";
System.out.println("Infix : " + convert(exp));
}
}
|
Python3
def prefixToInfix(prefix):
stack = []
i = len(prefix) - 1
while i >= 0:
if not isOperator(prefix[i]):
stack.append(prefix[i])
i -= 1
else:
str = "(" + stack.pop() + prefix[i] + stack.pop() + ")"
stack.append(str)
i -= 1
return stack.pop()
def isOperator(c):
if c == "*" or c == "+" or c == "-" or c == "/" or c == "^" or c == "(" or c == ")":
return True
else:
return False
if __name__=="__main__":
str = "*-A/BC-/AKL"
print(prefixToInfix(str))
|
C#
using System;
using System.Collections;
class GFG{
static bool isOperator(char x)
{
switch(x)
{
case '+':
case '-':
case '*':
case '/':
case '^':
case '%':
return true;
}
return false;
}
public static string convert(string str)
{
Stack stack = new Stack();
int l = str.Length;
for(int i = l - 1; i >= 0; i--)
{
char c = str[i];
if (isOperator(c))
{
string op1 = (string)stack.Pop();
string op2 = (string)stack.Pop();
string temp = "(" + op1 + c + op2 + ")";
stack.Push(temp);
}
else
{
stack.Push(c + "");
}
}
return (string)stack.Pop();
}
public static void Main(string[] args)
{
string exp = "*-A/BC-/AKL";
Console.Write("Infix : " + convert(exp));
}
}
|
Javascript
<script>
function isOperator(x)
{
switch(x)
{
case '+':
case '-':
case '*':
case '/':
case '^':
case '%':
return true;
}
return false;
}
function convert(str)
{
let stack = [];
let l = str.length;
for(let i = l - 1; i >= 0; i--)
{
let c = str[i];
if (isOperator(c))
{
let op1 = stack[stack.length - 1];
stack.pop()
let op2 = stack[stack.length - 1];
stack.pop()
let temp = "(" + op1 + c + op2 + ")";
stack.push(temp);
}
else
{
stack.push(c + "");
}
}
return stack[stack.length - 1];
}
let exp = "*-A/BC-/AKL";
document.write("Infix : " + convert(exp));
</script>
|
Output
Infix : ((A-(B/C))*((A/K)-L))
Time Complexity: O(n)
Auxiliary Space: O(n)
------
Postfix to Prefix Conversion
Postfix: An expression is called the postfix expression if the operator appears in the expression after the operands. Simply of the form (operand1 operand2 operator).
Example : AB+CD-* (Infix : (A+B) * (C-D) )
Prefix : An expression is called the prefix expression if the operator appears in the expression before the operands. Simply of the form (operator operand1 operand2).
Example : *+AB-CD (Infix : (A+B) * (C-D) )
Given a Postfix expression, convert it into a Prefix expression.
Conversion of Postfix expression directly to Prefix without going through the process of converting them first to Infix and then to Prefix is much better in terms of computation and better understanding the expression (Computers evaluate using Postfix expression).
Examples:
Input : Postfix : AB+CD-*
Output : Prefix : *+AB-CD
Explanation : Postfix to Infix : (A+B) * (C-D)
Infix to Prefix : *+AB-CD
Input : Postfix : ABC/-AK/L-*
Output : Prefix : *-A/BC-/AKL
Explanation : Postfix to Infix : ((A-(B/C))*((A/K)-L))
Infix to Prefix : *-A/BC-/AKL
Algorithm for Postfix to Prefix:
- Read the Postfix expression from left to right
- If the symbol is an operand, then push it onto the Stack
- If the symbol is an operator, then pop two operands from the Stack
Create a string by concatenating the two operands and the operator before them.
string = operator + operand2 + operand1
And push the resultant string back to Stack
- Repeat the above steps until end of Postfix expression.
Below is the implementation of the above idea:
C++
#include <bits/stdc++.h>
using namespace std;
bool isOperator(char x)
{
switch (x) {
case '+':
case '-':
case '/':
case '*':
return true;
}
return false;
}
string postToPre(string post_exp)
{
stack<string> s;
int length = post_exp.size();
for (int i = 0; i < length; i++) {
if (isOperator(post_exp[i])) {
string op1 = s.top();
s.pop();
string op2 = s.top();
s.pop();
string temp = post_exp[i] + op2 + op1;
s.push(temp);
}
else {
s.push(string(1, post_exp[i]));
}
}
string ans = "";
while (!s.empty()) {
ans += s.top();
s.pop();
}
return ans;
}
int main()
{
string post_exp = "ABC/-AK/L-*";
cout << "Prefix : " << postToPre(post_exp);
return 0;
}
|
Java
import java.util.*;
class GFG {
static boolean isOperator(char x)
{
switch (x) {
case '+':
case '-':
case '/':
case '*':
return true;
}
return false;
}
static String postToPre(String post_exp)
{
Stack<String> s = new Stack<String>();
int length = post_exp.length();
for (int i = 0; i < length; i++) {
if (isOperator(post_exp.charAt(i))) {
String op1 = s.peek();
s.pop();
String op2 = s.peek();
s.pop();
String temp
= post_exp.charAt(i) + op2 + op1;
s.push(temp);
}
else {
s.push(post_exp.charAt(i) + "");
}
}
String ans = "";
for (String i : s)
ans += i;
return ans;
}
public static void main(String args[])
{
String post_exp = "ABC/-AK/L-*";
System.out.println("Prefix : "
+ postToPre(post_exp));
}
}
|
Python3
def isOperator(x):
if x == "+":
return True
if x == "-":
return True
if x == "/":
return True
if x == "*":
return True
return False
def postToPre(post_exp):
s = []
length = len(post_exp)
for i in range(length):
if (isOperator(post_exp[i])):
op1 = s[-1]
s.pop()
op2 = s[-1]
s.pop()
temp = post_exp[i] + op2 + op1
s.append(temp)
else:
s.append(post_exp[i])
ans = ""
for i in s:
ans += i
return ans
if __name__ == "__main__":
post_exp = "AB+CD-"
print("Prefix : ", postToPre(post_exp))
|
C#
using System;
using System.Collections;
class GFG {
static Boolean isOperator(char x)
{
switch (x) {
case '+':
case '-':
case '/':
case '*':
return true;
}
return false;
}
static String postToPre(String post_exp)
{
Stack s = new Stack();
int length = post_exp.Length;
for (int i = 0; i < length; i++) {
if (isOperator(post_exp[i])) {
String op1 = (String)s.Peek();
s.Pop();
String op2 = (String)s.Peek();
s.Pop();
String temp = post_exp[i] + op2 + op1;
s.Push(temp);
}
else {
s.Push(post_exp[i] + "");
}
}
String ans = "";
while (s.Count > 0)
ans += s.Pop();
return ans;
}
public static void Main(String[] args)
{
String post_exp = "ABC/-AK/L-*";
Console.WriteLine("Prefix : "
+ postToPre(post_exp));
}
}
|
Javascript
<script>
function isOperator(x)
{
switch (x) {
case '+':
case '-':
case '/':
case '*':
return true;
}
return false;
}
function postToPre(post_exp)
{
let s = [];
let length = post_exp.length;
for (let i = 0; i < length; i++) {
if (isOperator(post_exp[i])) {
let op1 = s[s.length - 1];
s.pop();
let op2 = s[s.length - 1];
s.pop();
let temp = post_exp[i] + op2 + op1;
s.push(temp);
}
else {
s.push(post_exp[i] + "");
}
}
let ans = "";
while (s.length > 0)
ans += s.pop();
return ans;
}
let post_exp = "ABC/-AK/L-*";
document.write("Prefix : " + postToPre(post_exp));
</script>
|
Output
Prefix : *-A/BC-/AKL
Time Complexity: O(N) // In the above-given approach, there is one loop for iterating over string which takes O(N) time in worst case. Therefore, the time complexity for this approach will be O(N).
Auxiliary Space: O(N) // we are using an empty stack as well as empty string to store the expression hence space taken is linear
------
Prefix to Postfix Conversion
Given a Prefix expression, convert it into a Postfix expression.
Conversion of Prefix expression directly to Postfix without going through the process of converting them first to Infix and then to Postfix is much better in terms of computation and better understanding the expression (Computers evaluate using Postfix expression).
let’s discuss about Prefix and Postfix notation:
Prefix: An expression is called the prefix expression if the operator appears in the expression before the operands. Simply of the form (operator operand1 operand2).
Example : *+AB-CD (Infix : (A+B) * (C-D) )
Postfix: An expression is called the postfix expression if the operator appears in the expression after the operands. Simply of the form (operand1 operand2 operator).
Example : AB+CD-* (Infix : (A+B * (C-D) )
Note : Follow the link for prefix to postfix online convertor.
Examples:
Input : Prefix : *+AB-CD
Output : Postfix : AB+CD-*
Explanation : Prefix to Infix : (A+B) * (C-D)
Infix to Postfix : AB+CD-*
Input : Prefix : *-A/BC-/AKL
Output : Postfix : ABC/-AK/L-*
Explanation : Prefix to Infix : (A-(B/C))*((A/K)-L)
Infix to Postfix : ABC/-AK/L-*
Algorithm for Prefix to Postfix:
- Read the Prefix expression in reverse order (from right to left)
- If the symbol is an operand, then push it onto the Stack
- If the symbol is an operator, then pop two operands from the Stack
Create a string by concatenating the two operands and the operator after them.
string = operand1 + operand2 + operator
And push the resultant string back to Stack
- Repeat the above steps until end of Prefix expression.
Code for Prefix to postfix conversion:
C++
#include <iostream>
#include <stack>
using namespace std;
bool isOperator(char x)
{
switch (x) {
case '+':
case '-':
case '/':
case '*':
return true;
}
return false;
}
string preToPost(string pre_exp)
{
stack<string> s;
int length = pre_exp.size();
for (int i = length - 1; i >= 0; i--)
{
if (isOperator(pre_exp[i]))
{
string op1 = s.top();
s.pop();
string op2 = s.top();
s.pop();
string temp = op1 + op2 + pre_exp[i];
s.push(temp);
}
else {
s.push(string(1, pre_exp[i]));
}
}
return s.top();
}
int main()
{
string pre_exp = "*-A/BC-/AKL";
cout << "Postfix : " << preToPost(pre_exp);
return 0;
}
|
Java
import java.util.*;
class GFG {
static boolean isOperator(char x)
{
switch (x) {
case '+':
case '-':
case '/':
case '*':
return true;
}
return false;
}
static String preToPost(String pre_exp)
{
Stack<String> s = new Stack<String>();
int length = pre_exp.length();
for (int i = length - 1; i >= 0; i--)
{
if (isOperator(pre_exp.charAt(i)))
{
String op1 = s.peek();
s.pop();
String op2 = s.peek();
s.pop();
String temp = op1 + op2 + pre_exp.charAt(i);
s.push(temp);
}
else {
s.push(pre_exp.charAt(i) + "");
}
}
return s.peek();
}
public static void main(String args[])
{
String pre_exp = "*-A/BC-/AKL";
System.out.println("Postfix : "
+ preToPost(pre_exp));
}
}
|
Python 3
s = "*-A/BC-/AKL"
stack = []
operators = set(['+', '-', '*', '/', '^'])
s = s[::-1]
for i in s:
if i in operators:
a = stack.pop()
b = stack.pop()
temp = a+b+i
stack.append(temp)
else:
stack.append(i)
print(*stack)
|
C#
using System;
using System.Collections.Generic;
class GFG {
static bool isOperator(char x)
{
switch (x) {
case '+':
case '-':
case '/':
case '*':
return true;
}
return false;
}
static String preToPost(String pre_exp)
{
Stack<String> s = new Stack<String>();
int length = pre_exp.Length;
for (int i = length - 1; i >= 0; i--)
{
if (isOperator(pre_exp[i]))
{
String op1 = s.Peek();
s.Pop();
String op2 = s.Peek();
s.Pop();
String temp = op1 + op2 + pre_exp[i];
s.Push(temp);
}
else {
s.Push(pre_exp[i] + "");
}
}
return s.Peek();
}
public static void Main(String[] args)
{
String pre_exp = "*-A/BC-/AKL";
Console.WriteLine("Postfix : "
+ preToPost(pre_exp));
}
}
|
Javascript
<script>
function isOperator(x)
{
switch (x) {
case '+':
case '-':
case '/':
case '*':
return true;
}
return false;
}
function preToPost(pre_exp)
{
let s = [];
let length = pre_exp.length;
for (let i = length - 1; i >= 0; i--)
{
if (isOperator(pre_exp[i]))
{
let op1 = s[s.length - 1];
s.pop();
let op2 = s[s.length - 1];
s.pop();
let temp = op1 + op2 + pre_exp[i];
s.push(temp);
}
else {
s.push(pre_exp[i] + "");
}
}
return s[s.length - 1];
}
let pre_exp = "*-A/BC-/AKL";
document.write("Postfix : " + preToPost(pre_exp));
</script>
|
Output
Postfix : ABC/-AK/L-*
Time Complexity: O(N), as we are using a loop for traversing the expression.
Auxiliary Space: O(N), as we are using stack for extra space.
------
Evaluation of Postfix Expression
Given a postfix expression, the task is to evaluate the postfix expression.
Postfix expression: The expression of the form “a b operator” (ab+) i.e., when a pair of operands is followed by an operator.
Examples:
Input: str = “2 3 1 * + 9 -“
Output: -4
Explanation: If the expression is converted into an infix expression, it will be 2 + (3 * 1) – 9 = 5 – 9 = -4.
Input: str = “100 200 + 2 / 5 * 7 +”
Output: 757
Evaluation of Postfix Expression using Stack:
To evaluate a postfix expression we can use a stack.
Iterate the expression from left to right and keep on storing the operands into a stack. Once an operator is received, pop the two topmost elements and evaluate them and push the result in the stack again.
Illustration:
Follow the below illustration for a better understanding:
Consider the expression: exp = “2 3 1 * + 9 -“
- Scan 2, it’s a number, So push it into stack. Stack contains ‘2’.
Push 2 into stack
- Scan 3, again a number, push it to stack, stack now contains ‘2 3’ (from bottom to top)
Push 3 into stack
- Scan 1, again a number, push it to stack, stack now contains ‘2 3 1’
Push 1 into stack
- Scan *, it’s an operator. Pop two operands from stack, apply the * operator on operands. We get 3*1 which results in 3. We push the result 3 to stack. The stack now becomes ‘2 3’.
Evaluate * operator and push result in stack
- Scan +, it’s an operator. Pop two operands from stack, apply the + operator on operands. We get 3 + 2 which results in 5. We push the result 5 to stack. The stack now becomes ‘5’.
Evaluate + operator and push result in stack
- Scan 9, it’s a number. So we push it to the stack. The stack now becomes ‘5 9’.
Push 9 into stack
- Scan -, it’s an operator, pop two operands from stack, apply the – operator on operands, we get 5 – 9 which results in -4. We push the result -4 to the stack. The stack now becomes ‘-4’.
Evaluate ‘-‘ operator and push result in stack
- There are no more elements to scan, we return the top element from the stack (which is the only element left in a stack).
So the result becomes -4.
Follow the steps mentioned below to evaluate postfix expression using stack:
- Create a stack to store operands (or values).
- Scan the given expression from left to right and do the following for every scanned element.
- If the element is a number, push it into the stack.
- If the element is an operator, pop operands for the operator from the stack. Evaluate the operator and push the result back to the stack.
- When the expression is ended, the number in the stack is the final answer.
Below is the implementation of the above approach:
C
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct Stack {
int top;
unsigned capacity;
int* array;
};
struct Stack* createStack(unsigned capacity)
{
struct Stack* stack
= (struct Stack*)malloc(sizeof(struct Stack));
if (!stack)
return NULL;
stack->top = -1;
stack->capacity = capacity;
stack->array
= (int*)malloc(stack->capacity * sizeof(int));
if (!stack->array)
return NULL;
return stack;
}
int isEmpty(struct Stack* stack)
{
return stack->top == -1;
}
char peek(struct Stack* stack)
{
return stack->array[stack->top];
}
char pop(struct Stack* stack)
{
if (!isEmpty(stack))
return stack->array[stack->top--];
return '$';
}
void push(struct Stack* stack, char op)
{
stack->array[++stack->top] = op;
}
int evaluatePostfix(char* exp)
{
struct Stack* stack = createStack(strlen(exp));
int i;
if (!stack)
return -1;
for (i = 0; exp[i]; ++i) {
if (isdigit(exp[i]))
push(stack, exp[i] - '0');
else {
int val1 = pop(stack);
int val2 = pop(stack);
switch (exp[i]) {
case '+':
push(stack, val2 + val1);
break;
case '-':
push(stack, val2 - val1);
break;
case '*':
push(stack, val2 * val1);
break;
case '/':
push(stack, val2 / val1);
break;
}
}
}
return pop(stack);
}
int main()
{
char exp[] = "231*+9-";
printf("postfix evaluation: %d", evaluatePostfix(exp));
return 0;
}
|
C++
#include <bits/stdc++.h>
using namespace std;
int evaluatePostfix(string exp)
{
stack<int> st;
for (int i = 0; i < exp.size(); ++i) {
if (isdigit(exp[i]))
st.push(exp[i] - '0');
else {
int val1 = st.top();
st.pop();
int val2 = st.top();
st.pop();
switch (exp[i]) {
case '+':
st.push(val2 + val1);
break;
case '-':
st.push(val2 - val1);
break;
case '*':
st.push(val2 * val1);
break;
case '/':
st.push(val2 / val1);
break;
}
}
}
return st.top();
}
int main()
{
string exp = "231*+9-";
cout << "postfix evaluation: " << evaluatePostfix(exp);
return 0;
}
|
Java
import java.util.Stack;
public class Test {
static int evaluatePostfix(String exp)
{
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < exp.length(); i++) {
char c = exp.charAt(i);
if (Character.isDigit(c))
stack.push(c - '0');
else {
int val1 = stack.pop();
int val2 = stack.pop();
switch (c) {
case '+':
stack.push(val2 + val1);
break;
case '-':
stack.push(val2 - val1);
break;
case '/':
stack.push(val2 / val1);
break;
case '*':
stack.push(val2 * val1);
break;
}
}
}
return stack.pop();
}
public static void main(String[] args)
{
String exp = "231*+9-";
System.out.println("postfix evaluation: "
+ evaluatePostfix(exp));
}
}
|
Python3
class Evaluate:
def __init__(self, capacity):
self.top = -1
self.capacity = capacity
self.array = []
def isEmpty(self):
return True if self.top == -1 else False
def peek(self):
return self.array[-1]
def pop(self):
if not self.isEmpty():
self.top -= 1
return self.array.pop()
else:
return "$"
def push(self, op):
self.top += 1
self.array.append(op)
def evaluatePostfix(self, exp):
for i in exp:
if i.isdigit():
self.push(i)
else:
val1 = self.pop()
val2 = self.pop()
self.push(str(eval(val2 + i + val1)))
return int(self.pop())
if __name__ == '__main__':
exp = "231*+9-"
obj = Evaluate(len(exp))
print("postfix evaluation: %d" % (obj.evaluatePostfix(exp)))
|
C#
using System;
using System.Collections;
namespace GFG {
class Geek {
static void Main()
{
Geek e = new Geek();
e.v = ("231*+9-");
e.expression();
Console.WriteLine("postfix evaluation: "
+ e.answer);
Console.Read();
}
public string v;
public string answer;
Stack i = new Stack();
public void expression()
{
int a, b, ans;
for (int j = 0; j < v.Length; j++)
{
String c = v.Substring(j, 1);
if (c.Equals("*")) {
String sa = (String)i.Pop();
String sb = (String)i.Pop();
a = Convert.ToInt32(sb);
b = Convert.ToInt32(sa);
ans = a * b;
i.Push(ans.ToString());
}
else if (c.Equals("/")) {
String sa = (String)i.Pop();
String sb = (String)i.Pop();
a = Convert.ToInt32(sb);
b = Convert.ToInt32(sa);
ans = a / b;
i.Push(ans.ToString());
}
else if (c.Equals("+")) {
String sa = (String)i.Pop();
String sb = (String)i.Pop();
a = Convert.ToInt32(sb);
b = Convert.ToInt32(sa);
ans = a + b;
i.Push(ans.ToString());
}
else if (c.Equals("-")) {
String sa = (String)i.Pop();
String sb = (String)i.Pop();
a = Convert.ToInt32(sb);
b = Convert.ToInt32(sa);
ans = a - b;
i.Push(ans.ToString());
}
else {
i.Push(v.Substring(j, 1));
}
}
answer = (String)i.Pop();
}
}
}
|
Javascript
<script>
function evaluatePostfix(exp)
{
let stack=[];
for(let i=0;i<exp.length;i++)
{
let c=exp[i];
if(! isNaN( parseInt(c) ))
stack.push(c.charCodeAt(0) - '0'.charCodeAt(0));
else
{
let val1 = stack.pop();
let val2 = stack.pop();
switch(c)
{
case '+':
stack.push(val2+val1);
break;
case '-':
stack.push(val2- val1);
break;
case '/':
stack.push(val2/val1);
break;
case '*':
stack.push(val2*val1);
break;
}
}
}
return stack.pop();
}
let exp="231*+9-";
document.write("postfix evaluation: "+evaluatePostfix(exp));
</script>
|
Output
postfix evaluation: -4
Time Complexity: O(N)
Auxiliary Space: O(N)
There are the following limitations of the above implementation.
- It supports only 4 binary operators ‘+’, ‘*’, ‘-‘ and ‘/’. It can be extended for more operators by adding more switch cases.
- The allowed operands are only single-digit operands.
Postfix evaluation for multi-digit numbers:
The above program can be extended for multiple digits by adding a separator-like space between all elements (operators and operands) of the given expression.
Below given is the extended program which allows operands to have multiple digits.
C
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct Stack {
int top;
unsigned capacity;
int* array;
};
struct Stack* createStack(unsigned capacity)
{
struct Stack* stack
= (struct Stack*)malloc(sizeof(struct Stack));
if (!stack)
return NULL;
stack->top = -1;
stack->capacity = capacity;
stack->array
= (int*)malloc(stack->capacity * sizeof(int));
if (!stack->array)
return NULL;
return stack;
}
int isEmpty(struct Stack* stack)
{
return stack->top == -1;
}
int peek(struct Stack* stack)
{
return stack->array[stack->top];
}
int pop(struct Stack* stack)
{
if (!isEmpty(stack))
return stack->array[stack->top--];
return '$';
}
void push(struct Stack* stack, int op)
{
stack->array[++stack->top] = op;
}
int evaluatePostfix(char* exp)
{
struct Stack* stack = createStack(strlen(exp));
int i;
if (!stack)
return -1;
for (i = 0; exp[i]; ++i) {
if (exp[i] == ' ')
continue;
else if (isdigit(exp[i])) {
int num = 0;
while (isdigit(exp[i])) {
num = num * 10 + (int)(exp[i] - '0');
i++;
}
i--;
push(stack, num);
}
else {
int val1 = pop(stack);
int val2 = pop(stack);
switch (exp[i]) {
case '+':
push(stack, val2 + val1);
break;
case '-':
push(stack, val2 - val1);
break;
case '*':
push(stack, val2 * val1);
break;
case '/':
push(stack, val2 / val1);
break;
}
}
}
return pop(stack);
}
int main()
{
char exp[] = "100 200 + 2 / 5 * 7 +";
printf("%d", evaluatePostfix(exp));
return 0;
}
|
C++14
#include <bits/stdc++.h>
using namespace std;
int evaluatePostfix(char* exp)
{
stack<int> st;
int i;
for (i = 0; exp[i]; ++i) {
if (exp[i] == ' ')
continue;
else if (isdigit(exp[i])) {
int num = 0;
while (isdigit(exp[i])) {
num = num * 10 + (int)(exp[i] - '0');
i++;
}
i--;
st.push(num);
}
else {
int val1 = st.top();
st.pop();
int val2 = st.top();
st.pop();
switch (exp[i]) {
case '+':
st.push(val2 + val1);
break;
case '-':
st.push(val2 - val1);
break;
case '*':
st.push(val2 * val1);
break;
case '/':
st.push(val2 / val1);
break;
}
}
}
return st.top();
}
int main()
{
char exp[] = "100 200 + 2 / 5 * 7 +";
cout << evaluatePostfix(exp);
return 0;
}
|
Java
import java.util.Stack;
class Test1 {
static int evaluatePostfix(String exp)
{
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < exp.length(); i++) {
char c = exp.charAt(i);
if (c == ' ')
continue;
else if (Character.isDigit(c)) {
int n = 0;
while (Character.isDigit(c)) {
n = n * 10 + (int)(c - '0');
i++;
c = exp.charAt(i);
}
i--;
stack.push(n);
}
else {
int val1 = stack.pop();
int val2 = stack.pop();
switch (c) {
case '+':
stack.push(val2 + val1);
break;
case '-':
stack.push(val2 - val1);
break;
case '/':
stack.push(val2 / val1);
break;
case '*':
stack.push(val2 * val1);
break;
}
}
}
return stack.pop();
}
public static void main(String[] args)
{
String exp = "100 200 + 2 / 5 * 7 +";
System.out.println(evaluatePostfix(exp));
}
}
|
Python3
class evalpostfix:
def __init__(self):
self.stack = []
self.top = -1
def pop(self):
if self.top == -1:
return
else:
self.top -= 1
return self.stack.pop()
def push(self, i):
self.top += 1
self.stack.append(i)
def centralfunc(self, ab):
for i in ab:
try:
self.push(int(i))
except ValueError:
val1 = self.pop()
val2 = self.pop()
if i == '/':
self.push(val2 / val1)
else:
switcher = {'+': val2 + val1, '-': val2 -
val1, '*': val2 * val1, '^': val2**val1}
self.push(switcher.get(i))
return int(self.pop())
if __name__ == '__main__':
str = '100 200 + 2 / 5 * 7 +'
strconv = str.split(' ')
obj = evalpostfix()
print(obj.centralfunc(strconv))
|
C#
using System;
using System.Collections.Generic;
class GFG {
public static int evaluatePostfix(string exp)
{
Stack<int> stack = new Stack<int>();
for (int i = 0; i < exp.Length; i++) {
char c = exp[i];
if (c == ' ') {
continue;
}
else if (char.IsDigit(c)) {
int n = 0;
while (char.IsDigit(c)) {
n = n * 10 + (int)(c - '0');
i++;
c = exp[i];
}
i--;
stack.Push(n);
}
else {
int val1 = stack.Pop();
int val2 = stack.Pop();
switch (c) {
case '+':
stack.Push(val2 + val1);
break;
case '-':
stack.Push(val2 - val1);
break;
case '/':
stack.Push(val2 / val1);
break;
case '*':
stack.Push(val2 * val1);
break;
}
}
}
return stack.Pop();
}
public static void Main(string[] args)
{
string exp = "100 200 + 2 / 5 * 7 +";
Console.WriteLine(evaluatePostfix(exp));
}
}
|
Javascript
<script>
function evaluatePostfix(exp)
{
let stack = [];
for (let i = 0; i < exp.length; i++)
{
let c = exp[i];
if (c == ' ')
{
continue;
}
else if (c >= '0' && c <= '9')
{
let n = 0;
while (c >= '0' && c <= '9')
{
n = n * 10 + (c - '0');
i++;
c = exp[i];
}
i--;
stack.push(n);
}
else
{
let val1 = stack.pop();
let val2 = stack.pop();
switch (c)
{
case '+':
stack.push(val2 + val1);
break;
case '-':
stack.push(val2 - val1);
break;
case '/':
stack.push(parseInt(val2 / val1, 10));
break;
case '*':
stack.push(val2 * val1);
break;
}
}
}
return stack.pop();
}
let exp = "100 200 + 2 / 5 * 7 +";
document.write(evaluatePostfix(exp));
</script>
|
Time Complexity: O(N)
Auxiliary Space: O(N)
------
Tree Traversal Techniques – Data Structure and Algorithm Tutorials
Tree Traversal techniques include various ways to visit all the nodes of the tree. Unlike linear data structures (Array, Linked List, Queues, Stacks, etc) which have only one logical way to traverse them, trees can be traversed in different ways. In this article, we will discuss about all the tree traversal techniques along with their uses.
.webp)
Tree Traversal Meaning:
Tree Traversal refers to the process of visiting or accessing each node of the tree exactly once in a certain order. Tree traversal algorithms help us to visit and process all the nodes of the tree. Since tree is not a linear data structure, there are multiple nodes which we can visit after visiting a certain node. There are multiple tree traversal techniques which decide the order in which the nodes of the tree are to be visited.
Tree Traversal Techniques:
A Tree Data Structure can be traversed in following ways:
- Depth First Search or DFS
- Inorder Traversal
- Preorder Traversal
- Postorder Traversal
- Level Order Traversal or Breadth First Search or BFS
Inorder traversal visits the node in the order: Left -> Root -> Right
Algorithm for Inorder Traversal:
Inorder(tree)
- Traverse the left subtree, i.e., call Inorder(left->subtree)
- Visit the root.
- Traverse the right subtree, i.e., call Inorder(right->subtree)
Uses of Inorder Traversal:
- In the case of binary search trees (BST), Inorder traversal gives nodes in non-decreasing order.
- To get nodes of BST in non-increasing order, a variation of Inorder traversal where Inorder traversal is reversed can be used.
- Inorder traversal can be used to evaluate arithmetic expressions stored in expression trees.
Code Snippet for Inorder Traversal:
// Given a binary tree, print its nodes in inorder
void printInorder(struct Node* node)
{
if (node == NULL)
return;
// First recur on left child
printInorder(node->left);
// Then print the data of node
cout << node->data << " ";
// Now recur on right child
printInorder(node->right);
}
void printInorder(Node node)
{
if (node == null)
return;
// First recur on left child
printInorder(node.left);
// Then print the data of node
System.out.print(node.key + " ");
// Now recur on right child
printInorder(node.right);
}
OutputInorder traversal of binary tree is
4 2 5 1 3
Time Complexity: O(N)
Auxiliary Space: If we don’t consider the size of the stack for function calls then O(1) otherwise O(h) where h is the height of the tree.
Preorder traversal visits the node in the order: Root -> Left -> Right
Algorithm for Preorder Traversal:
Preorder(tree)
- Visit the root.
- Traverse the left subtree, i.e., call Preorder(left->subtree)
- Traverse the right subtree, i.e., call Preorder(right->subtree)
Uses of Preorder Traversal:
- Preorder traversal is used to create a copy of the tree.
- Preorder traversal is also used to get prefix expressions on an expression tree.
Code Snippet for Preorder Traversal:
// Given a binary tree, print its nodes in preorder
void printPreorder(struct Node* node)
{
if (node == NULL)
return;
// First print data of node
cout << node->data << " ";
// Then recur on left subtree
printPreorder(node->left);
// Now recur on right subtree
printPreorder(node->right);
}
// Given a binary tree, print its nodes in preorder
void printPreorder(Node node)
{
if (node == null)
return;
// First print data of node
System.out.print(node.key + " ");
// Then recur on left subtree
printPreorder(node.left);
// Now recur on right subtree
printPreorder(node.right);
}
OutputPreorder traversal of binary tree is
1 2 4 5 3
Time Complexity: O(N)
Auxiliary Space: If we don’t consider the size of the stack for function calls then O(1) otherwise O(h) where h is the height of the tree.
Postorder traversal visits the node in the order: Left -> Right -> Root
Algorithm for Postorder Traversal:
Algorithm Postorder(tree)
- Traverse the left subtree, i.e., call Postorder(left->subtree)
- Traverse the right subtree, i.e., call Postorder(right->subtree)
- Visit the root
Uses of Postorder Traversal:
- Postorder traversal is used to delete the tree. See the question for the deletion of a tree for details.
- Postorder traversal is also useful to get the postfix expression of an expression tree.
- Postorder traversal can help in garbage collection algorithms, particularly in systems where manual memory management is used.
Code Snippet for Postorder Traversal:
// Given a binary tree, print its nodes according to the
// "bottom-up" postorder traversal.
void printPostorder(struct Node* node)
{
if (node == NULL)
return;
// First recur on left subtree
printPostorder(node->left);
// Then recur on right subtree
printPostorder(node->right);
// Now deal with the node
cout << node->data << " ";
}
// Given a binary tree, print its nodes according to the
// "bottom-up" postorder traversal.
void printPostorder(Node node)
{
if (node == null)
return;
// First recur on left subtree
printPostorder(node.left);
// Then recur on right subtree
printPostorder(node.right);
// Now deal with the node
System.out.print(node.key + " ");
}
OutputPostorder traversal of binary tree is
4 5 2 3 1
Level Order Traversal visits all nodes present in the same level completely before visiting the next level.
Algorithm for Level Order Traversal:
LevelOrder(tree)
- Create an empty queue Q
- Enqueue the root node of the tree to Q
- Loop while Q is not empty
- Dequeue a node from Q and visit it
- Enqueue the left child of the dequeued node if it exists
- Enqueue the right child of the dequeued node if it exists
Uses of Level Order:
Code Snippet for Level Order Traversal:
// Iterative method to find height of Binary Tree
void printLevelOrder(Node* root)
{
// Base Case
if (root == NULL)
return;
// Create an empty queue for level order traversal
queue<Node*> q;
// Enqueue Root and initialize height
q.push(root);
while (q.empty() == false) {
// Print front of queue and remove it from queue
Node* node = q.front();
cout << node->data << " ";
q.pop();
// Enqueue left child
if (node->left != NULL)
q.push(node->left);
// Enqueue right child
if (node->right != NULL)
q.push(node->right);
}
}
// Given a binary tree. Print
// its nodes in level order
// using array for implementing queue
void printLevelOrder()
{
Queue<Node> queue = new LinkedList<Node>();
queue.add(root);
while (!queue.isEmpty()) {
// poll() removes the present head.
Node tempNode = queue.poll();
System.out.print(tempNode.data + " ");
// Enqueue left child
if (tempNode.left != null) {
queue.add(tempNode.left);
}
// Enqueue right child
if (tempNode.right != null) {
queue.add(tempNode.right);
}
}
}
Other Tree Traversals:
- Boundary Traversal
- Diagonal Traversal
Boundary Traversal of a Tree includes:
- left boundary (nodes on left excluding leaf nodes)
- leaves (consist of only the leaf nodes)
- right boundary (nodes on right excluding leaf nodes)
Algorithm for Boundary Traversal:
BoundaryTraversal(tree)
- If root is not null:
- Print root’s data
- PrintLeftBoundary(root->left) // Print the left boundary nodes
- PrintLeafNodes(root->left) // Print the leaf nodes of left subtree
- PrintLeafNodes(root->right) // Print the leaf nodes of right subtree
- PrintRightBoundary(root->right) // Print the right boundary nodes
Uses of Boundary Traversal:
- Boundary traversal helps visualize the outer structure of a binary tree, providing insights into its shape and boundaries.
- Boundary traversal provides a way to access and modify these nodes, enabling operations such as pruning or repositioning of boundary nodes.
In the Diagonal Traversal of a Tree, all the nodes in a single diagonal will be printed one by one.
Algorithm for Diagonal Traversal:
DiagonalTraversal(tree):
- If root is not null:
- Create an empty map
- DiagonalTraversalUtil(root, 0, M) // Call helper function with initial diagonal level 0
- For each key-value pair (diagonalLevel, nodes) in M:
- For each node in nodes:
- Print node’s data
DiagonalTraversalUtil(node, diagonalLevel, M):
- If node is null:
- Return
- If diagonalLevel is not present in M:
- Create a new list in M for diagonalLevel
- Append node’s data to the list at M[diagonalLevel]
- DiagonalTraversalUtil(node->left, diagonalLevel + 1, M) // Traverse left child with increased diagonal level
- DiagonalTraversalUtil(node->right, diagonalLevel, M) // Traverse right child with same diagonal level
Uses of Diagonal Traversal:
- Diagonal traversal helps in visualizing the hierarchical structure of binary trees, particularly in tree-based data structures like binary search trees (BSTs) and heap trees.
- Diagonal traversal can be utilized to calculate path sums along diagonals in a binary tree.
Frequently Asked Questions (FAQs) on Tree Traversal Techniques:
1. What are tree traversal techniques?
Tree traversal techniques are methods used to visit and process all nodes in a tree data structure. They allow you to access each node exactly once in a systematic manner.
2. What are the common types of tree traversal?
The common types of tree traversal are: Inorder traversal, Preorder traversal, Postorder traversal, Level order traversal (Breadth-First Search)
3. What is Inorder traversal?
Inorder traversal is a depth-first traversal method where nodes are visited in the order: left subtree, current node, right subtree.
4. What is preorder traversal?
Preorder traversal is a depth-first traversal method where nodes are visited in the order: current node, left subtree, right subtree.
5. What is postorder traversal?
Postorder traversal is a depth-first traversal method where nodes are visited in the order: left subtree, right subtree, current node.
6. What is level order traversal?
Level order traversal, also known as Breadth-First Search (BFS), visits nodes level by level, starting from the root and moving to the next level before traversing deeper.
7. When should I use each traversal technique?
Inorder traversal is often used for binary search trees to get nodes in sorted order.
Preorder traversal is useful for creating a copy of the tree.
Postorder traversal is commonly used in expression trees to evaluate expressions.
Level order traversal is helpful for finding the shortest path between nodes.
8. How do I implement tree traversal algorithms?
Tree traversal algorithms can be implemented recursively or iteratively, depending on the specific requirements and programming language being used.
9. Can tree traversal algorithms be applied to other tree-like structures?
Yes, tree traversal algorithms can be adapted to traverse other tree-like structures such as binary heaps, n-ary trees, and graphs represented as trees.
10. Are there any performance considerations when choosing a traversal technique?
Performance considerations depend on factors such as the size and shape of the tree, available memory, and specific operations being performed during traversal. In general, the choice of traversal technique may affect the efficiency of certain operations, so it’s important to choose the most suitable method for your specific use case.
Some other important Tutorials:
------
Binary Search Tree (BST) Traversals – Inorder, Preorder, Post Order
Given a Binary Search Tree, The task is to print the elements in inorder, preorder, and postorder traversal of the Binary Search Tree.
Input:
A Binary Search Tree
Output:
Inorder Traversal: 10 20 30 100 150 200 300
Preorder Traversal: 100 20 10 30 200 150 300
Postorder Traversal: 10 30 20 150 300 200 100
Input:
Binary Search Tree
Output:
Inorder Traversal: 8 12 20 22 25 30 40
Preorder Traversal: 22 12 8 20 30 25 40
Postorder Traversal: 8 20 12 25 40 30 22
Below is the idea to solve the problem:
At first traverse left subtree then visit the root and then traverse the right subtree.
Follow the below steps to implement the idea:
- Traverse left subtree
- Visit the root and print the data.
- Traverse the right subtree
The inorder traversal of the BST gives the values of the nodes in sorted order. To get the decreasing order visit the right, root, and left subtree.
Below is the implementation of the inorder traversal.
C++
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int data;
Node* left;
Node* right;
Node(int v)
{
this->data = v;
this->left = this->right = NULL;
}
};
void printInorder(Node* node)
{
if (node == NULL)
return;
printInorder(node->left);
cout << node->data << " ";
printInorder(node->right);
}
int main()
{
Node* root = new Node(100);
root->left = new Node(20);
root->right = new Node(200);
root->left->left = new Node(10);
root->left->right = new Node(30);
root->right->left = new Node(150);
root->right->right = new Node(300);
cout << "Inorder Traversal: ";
printInorder(root);
return 0;
}
|
Java
import java.io.*;
class Node {
int data;
Node left;
Node right;
Node(int v)
{
this.data = v;
this.left = this.right = null;
}
}
class GFG {
public static void printInorder(Node node)
{
if (node == null)
return;
printInorder(node.left);
System.out.print(node.data + " ");
printInorder(node.right);
}
public static void main(String[] args)
{
Node root = new Node(100);
root.left = new Node(20);
root.right = new Node(200);
root.left.left = new Node(10);
root.left.right = new Node(30);
root.right.left = new Node(150);
root.right.right = new Node(300);
System.out.print("Inorder Traversal: ");
printInorder(root);
}
}
|
Python3
class Node:
def __init__(self, v):
self.left = None
self.right = None
self.data = v
def printInorder(root):
if root:
printInorder(root.left)
print(root.data,end=" ")
printInorder(root.right)
if __name__ == "__main__":
root = Node(100)
root.left = Node(20)
root.right = Node(200)
root.left.left = Node(10)
root.left.right = Node(30)
root.right.left = Node(150)
root.right.right = Node(300)
print("Inorder Traversal:",end=" ")
printInorder(root)
|
C#
using System;
public class Node
{
public int data;
public Node left;
public Node right;
public Node(int v)
{
this.data = v;
this.left = this.right = null;
}
}
public class GFG
{
public static void printInorder(Node node)
{
if (node == null)
{
return;
}
GFG.printInorder(node.left);
Console.Write(node.data.ToString() + " ");
GFG.printInorder(node.right);
}
public static void Main(String[] args)
{
var root = new Node(100);
root.left = new Node(20);
root.right = new Node(200);
root.left.left = new Node(10);
root.left.right = new Node(30);
root.right.left = new Node(150);
root.right.right = new Node(300);
Console.Write("Inorder Traversal: ");
GFG.printInorder(root);
}
}
|
Javascript
class Node {
constructor(v) {
this.left = null;
this.right = null;
this.data = v;
}
}
function printInorder(root)
{
if (root)
{
printInorder(root.left);
console.log(root.data);
printInorder(root.right);
}
}
if (true)
{
let root = new Node(100);
root.left = new Node(20);
root.right = new Node(200);
root.left.left = new Node(10);
root.left.right = new Node(30);
root.right.left = new Node(150);
root.right.right = new Node(300);
console.log("Inorder Traversal:");
printInorder(root);
}
|
Output
Inorder Traversal: 10 20 30 100 150 200 300
Time complexity: O(N), Where N is the number of nodes.
Auxiliary Space: O(h), Where h is the height of tree
Below is the idea to solve the problem:
At first visit the root then traverse left subtree and then traverse the right subtree.
Follow the below steps to implement the idea:
- Visit the root and print the data.
- Traverse left subtree
- Traverse the right subtree
Below is the implementation of the preorder traversal.
C++
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int data;
Node* left;
Node* right;
Node(int v)
{
this->data = v;
this->left = this->right = NULL;
}
};
void printPreOrder(Node* node)
{
if (node == NULL)
return;
cout << node->data << " ";
printPreOrder(node->left);
printPreOrder(node->right);
}
int main()
{
Node* root = new Node(100);
root->left = new Node(20);
root->right = new Node(200);
root->left->left = new Node(10);
root->left->right = new Node(30);
root->right->left = new Node(150);
root->right->right = new Node(300);
cout << "Preorder Traversal: ";
printPreOrder(root);
return 0;
}
|
Java
import java.io.*;
class Node {
int data;
Node left;
Node right;
Node(int v)
{
this.data = v;
this.left = this.right = null;
}
}
class GFG {
public static void printPreorder(Node node)
{
if (node == null)
return;
System.out.print(node.data + " ");
printPreorder(node.left);
printPreorder(node.right);
}
public static void main(String[] args)
{
Node root = new Node(100);
root.left = new Node(20);
root.right = new Node(200);
root.left.left = new Node(10);
root.left.right = new Node(30);
root.right.left = new Node(150);
root.right.right = new Node(300);
System.out.print("Preorder Traversal: ");
printPreorder(root);
}
}
|
Python3
class Node:
def __init__(self, v):
self.data = v
self.left = None
self.right = None
def printPreOrder(node):
if node is None:
return
print(node.data, end = " ")
printPreOrder(node.left)
printPreOrder(node.right)
if __name__ == "__main__":
root = Node(100)
root.left = Node(20)
root.right = Node(200)
root.left.left = Node(10)
root.left.right = Node(30)
root.right.left = Node(150)
root.right.right = Node(300)
print("Preorder Traversal: ", end = "")
printPreOrder(root)
|
C#
using System;
public class Node
{
public int data;
public Node left;
public Node right;
public Node(int v)
{
this.data = v;
this.left = this.right = null;
}
}
public class GFG
{
public static void printPreorder(Node node)
{
if (node == null)
{
return;
}
Console.Write(node.data.ToString() + " ");
GFG.printPreorder(node.left);
GFG.printPreorder(node.right);
}
public static void Main(String[] args)
{
var root = new Node(100);
root.left = new Node(20);
root.right = new Node(200);
root.left.left = new Node(10);
root.left.right = new Node(30);
root.right.left = new Node(150);
root.right.right = new Node(300);
Console.Write("Preorder Traversal: ");
GFG.printPreorder(root);
}
}
|
Javascript
class Node {
constructor(v) {
this.data = v;
this.left = this.right = null;
}
}
function printPreOrder(node) {
if (node == null) return;
console.log(node.data + " ");
printPreOrder(node.left);
printPreOrder(node.right);
}
let root = new Node(100);
root.left = new Node(20);
root.right = new Node(200);
root.left.left = new Node(10);
root.left.right = new Node(30);
root.right.left = new Node(150);
root.right.right = new Node(300);
console.log("Preorder Traversal: ");
printPreOrder(root);
|
Output
Preorder Traversal: 100 20 10 30 200 150 300
Time complexity: O(N), Where N is the number of nodes.
Auxiliary Space: O(H), Where H is the height of the tree
Below is the idea to solve the problem:
At first traverse left subtree then traverse the right subtree and then visit the root.
Follow the below steps to implement the idea:
- Traverse left subtree
- Traverse the right subtree
- Visit the root and print the data.
Below is the implementation of the postorder traversal:
C++
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int data;
Node* left;
Node* right;
Node(int v)
{
this->data = v;
this->left = this->right = NULL;
}
};
void printPostOrder(Node* node)
{
if (node == NULL)
return;
printPostOrder(node->left);
printPostOrder(node->right);
cout << node->data << " ";
}
int main()
{
Node* root = new Node(100);
root->left = new Node(20);
root->right = new Node(200);
root->left->left = new Node(10);
root->left->right = new Node(30);
root->right->left = new Node(150);
root->right->right = new Node(300);
cout << "PostOrder Traversal: ";
printPostOrder(root);
cout << "\n";
return 0;
}
|
Java
import java.io.*;
class GFG {
static class Node {
int data;
Node left;
Node right;
Node(int v)
{
this.data = v;
this.left = this.right = null;
}
}
public static void printPreorder(Node node)
{
if (node == null)
return;
printPreorder(node.left);
printPreorder(node.right);
System.out.print(node.data + " ");
}
public static void main(String[] args)
{
Node root = new Node(100);
root.left = new Node(20);
root.right = new Node(200);
root.left.left = new Node(10);
root.left.right = new Node(30);
root.right.left = new Node(150);
root.right.right = new Node(300);
System.out.print("Preorder Traversal: ");
printPreorder(root);
}
}
|
C#
using System;
public class Node
{
public int data;
public Node left;
public Node right;
public Node(int v)
{
this.data = v;
this.left = this.right = null;
}
}
public class GFG
{
public static void printPreorder(Node node)
{
if (node == null)
{
return;
}
GFG.printPreorder(node.left);
GFG.printPreorder(node.right);
Console.Write(node.data.ToString() + " ");
}
public static void Main(String[] args)
{
var root = new Node(100);
root.left = new Node(20);
root.right = new Node(200);
root.left.left = new Node(10);
root.left.right = new Node(30);
root.right.left = new Node(150);
root.right.right = new Node(300);
Console.Write("Preorder Traversal: ");
GFG.printPreorder(root);
}
}
|
Python3
class Node:
def __init__(self, v):
self.data = v
self.left = None
self.right = None
def printPostOrder(node):
if node is None:
return
printPostOrder(node.left)
printPostOrder(node.right)
print(node.data, end = " ")
if __name__ == "__main__":
root = Node(100)
root.left = Node(20)
root.right = Node(200)
root.left.left = Node(10)
root.left.right = Node(30)
root.right.left = Node(150)
root.right.right = Node(300)
print("Postorder Traversal: ", end = "")
printPostOrder(root)
|
Javascript
class Node {
constructor(v) {
this.data = v;
this.left = null;
this.right = null;
}
}
function printPostOrder(node) {
if (node === null) {
return;
}
printPostOrder(node.left);
printPostOrder(node.right);
console.log(node.data, end = " ");
}
let root = new Node(100);
root.left = new Node(20);
root.right = new Node(200);
root.left.left = new Node(10);
root.left.right = new Node(30);
root.right.left = new Node(150);
root.right.right = new Node(300);
console.log("Postorder Traversal: ", end = "");
printPostOrder(root);
|
Output
PostOrder Traversal: 10 30 20 150 300 200 100
Time complexity: O(N), Where N is the number of nodes.
Auxiliary Space: O(H), Where H is the height of the tree
------