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

Table of Content

Infix Expressions
Advantages of Infix Expressions
Disadvantages Infix Expressions
Prefix Expressions (Polish Notation)
Advantages of Prefix Expressions
Disadvantages of Prefix Expressions
Postfix Expressions (Reverse Polish Notation)
Advantages of Postfix Notation
Disadvantages of Postfix Expressions
Comparison of Infix, Prefix and Postfix Expressions
Frequently Asked Questions on Infix, Postfix and Prefix Expressions

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

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 (Reverse Polish 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:**

Why do we need Prefix and Postfix notations?

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; // Function to return precedence of operators int prec(char c) { if (c == '^') return 3; else if (c == '/' || c == '*') return 2; else if (c == '+' || c == '-') return 1; else return -1; } // Function to return associativity of operators char associativity(char c) { if (c == '^') return 'R'; return 'L'; // Default to left-associative } // The main function to convert infix expression // to postfix expression void infixToPostfix(string s) { stack<char> st; string result; for (int i = 0; i < s.length(); i++) { char c = s[i]; // If the scanned character is // an operand, add it to the output string. if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9')) result += c; // If the scanned character is an // ‘(‘, push it to the stack. else if (c == '(') st.push('('); // If the scanned character is an ‘)’, // pop and add to the output string from the stack // until an ‘(‘ is encountered. else if (c == ')') { while (st.top() != '(') { result += st.top(); st.pop(); } st.pop(); // Pop '(' } // If an operator is scanned 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); } } // Pop all the remaining elements from the stack while (!st.empty()) { result += st.top(); st.pop(); } cout << result << endl; } // Driver code int main() { string exp = "a+b*(c^d-e)^(f+g*h)-i"; // Function call infixToPostfix(exp); return 0; } | | — |

C

| #include <stdio.h> #include <stdlib.h> #include <string.h> // Function to return precedence of operators int prec(char c) { if (c == '^') return 3; else if (c == '/' || c == '*') return 2; else if (c == '+' || c == '-') return 1; else return -1; } // Function to return associativity of operators char associativity(char c) { if (c == '^') return 'R'; return 'L'; // Default to left-associative } // The main function to convert infix expression to postfix expression 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 the scanned character is an operand, add it to the output string. if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9')) { result[resultIndex++] = c; } // If the scanned character is an ‘(‘, push it to the stack. else if (c == '(') { stack[++stackIndex] = c; } // If the scanned character is an ‘)’, pop and add to the output string from the stack // until an ‘(‘ is encountered. else if (c == ')') { while (stackIndex >= 0 && stack[stackIndex] != '(') { result[resultIndex++] = stack[stackIndex--]; } stackIndex--; // Pop '(' } // If an operator is scanned 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; } } // Pop all the remaining elements from the stack while (stackIndex >= 0) { result[resultIndex++] = stack[stackIndex--]; } result[resultIndex] = '\0'; printf("%s\n", result); } // Driver code int main() { char exp[] = "a+b*(c^d-e)^(f+g*h)-i"; // Function call infixToPostfix(exp); return 0; } | | — |

Java

| import java.util.Stack; public class InfixToPostfix { // Function to return precedence of operators static int prec(char c) { if (c == '^') return 3; else if (c == '/' || c == '*') return 2; else if (c == '+' || c == '-') return 1; else return -1; } // Function to return associativity of operators static char associativity(char c) { if (c == '^') return 'R'; return 'L'; // Default to left-associative } // The main function to convert infix expression to postfix expression 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 the scanned character is an operand, add it to the output string. if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9')) { result.append(c); } // If the scanned character is an ‘(‘, push it to the stack. else if (c == '(') { stack.push(c); } // If the scanned character is an ‘)’, pop and add to the output string from the stack // until an ‘(‘ is encountered. else if (c == ')') { while (!stack.isEmpty() && stack.peek() != '(') { result.append(stack.pop()); } stack.pop(); // Pop '(' } // If an operator is scanned 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); } } // Pop all the remaining elements from the stack while (!stack.isEmpty()) { result.append(stack.pop()); } System.out.println(result); } // Driver code public static void main(String[] args) { String exp = "a+b*(c^d-e)^(f+g*h)-i"; // Function call 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' # Default to left-associative def infix_to_postfix(s): result = [] stack = [] for i in range(len(s)): c = s[i] # If the scanned character is an operand, add it to the output string. if ('a' <= c <= 'z') or ('A' <= c <= 'Z') or ('0' <= c <= '9'): result.append(c) # If the scanned character is an ‘(‘, push it to the stack. elif c == '(': stack.append(c) # If the scanned character is an ‘)’, pop and add to the output string from the stack # until an ‘(‘ is encountered. elif c == ')': while stack and stack[-1] != '(': result.append(stack.pop()) stack.pop() # Pop '(' # If an operator is scanned 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) # Pop all the remaining elements from the stack while stack: result.append(stack.pop()) print(''.join(result)) # Driver code exp = "a+b*(c^d-e)^(f+g*h)-i" # Function call infix_to_postfix(exp) | | — |

C#

| using System; using System.Collections.Generic; class Program { // Function to return precedence of operators static int Prec(char c) { if (c == '^') return 3; else if (c == '/' || c == '*') return 2; else if (c == '+' || c == '-') return 1; else return -1; } // Function to return associativity of operators static char Associativity(char c) { if (c == '^') return 'R'; return 'L'; // Default to left-associative } // The main function to convert infix expression to postfix expression 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 the scanned character is an operand, add it to the output string. if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9')) { result.Add(c); } // If the scanned character is an ‘(‘, push it to the stack. else if (c == '(') { stack.Push(c); } // If the scanned character is an ‘)’, pop and add to the output string from the stack // until an ‘(‘ is encountered. else if (c == ')') { while (stack.Count > 0 && stack.Peek() != '(') { result.Add(stack.Pop()); } stack.Pop(); // Pop '(' } // If an operator is scanned 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); } } // Pop all the remaining elements from the stack while (stack.Count > 0) { result.Add(stack.Pop()); } Console.WriteLine(string.Join("", result)); } // Driver code static void Main() { string exp = "a+b*(c^d-e)^(f+g*h)-i"; // Function call InfixToPostfix(exp); } } | | — |

Javascript

| /* Javascript implementation to convert infix expression to postfix*/ //Function to return precedence of operators function prec(c) { if(c == '^') return 3; else if(c == '/' || c=='*') return 2; else if(c == '+' || c == '-') return 1; else return -1; } // The main function to convert infix expression //to postfix expression function infixToPostfix(s) { let st = []; //For stack operations, we are using JavaScript built in stack let result = ""; for(let i = 0; i < s.length; i++) { let c = s[i]; // If the scanned character is // an operand, add it to output string. if((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9')) result += c; // If the scanned character is an // ‘(‘, push it to the stack. else if(c == '(') st.push('('); // If the scanned character is an ‘)’, // pop and to output string from the stack // until an ‘(‘ is encountered. else if(c == ')') { while(st[st.length - 1] != '(') { result += st[st.length - 1]; st.pop(); } st.pop(); } //If an operator is scanned else { while(st.length != 0 && prec(s[i]) <= prec(st[st.length - 1])) { result += st[st.length - 1]; st.pop(); } st.push(c); } } // Pop all the remaining elements from the stack 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); // This code is contributed by decode2207. | | — |

Output

abcd^e-fgh*+^*+i-

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

Implement Stack and Queue using Deque

Prefix to Infix Conversion

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

| // C++ Program to convert prefix to Infix #include <iostream> #include <stack> using namespace std; // function to check if character is operator or not bool isOperator(char x) { switch (x) { case '+': case '-': case '/': case '*': case '^': case '%': return true; } return false; } // Convert prefix to Infix expression string preToInfix(string pre_exp) { stack<string> s; // length of expression int length = pre_exp.size(); // reading from right to left for (int i = length - 1; i >= 0; i--) { // check if symbol is operator if (isOperator(pre_exp[i])) { // pop two operands from stack string op1 = s.top(); s.pop(); string op2 = s.top(); s.pop(); // concat the operands and operator string temp = "(" + op1 + pre_exp[i] + op2 + ")"; // Push string temp back to stack s.push(temp); } // if symbol is an operand else { // push the operand to the stack s.push(string(1, pre_exp[i])); } } // Stack now contains the Infix expression return s.top(); } // Driver Code int main() { string pre_exp = "*-A/BC-/AKL"; cout << "Infix : " << preToInfix(pre_exp); return 0; } | | — |

Java

| // Java program to convert prefix to Infix import java.util.Stack; class GFG{ // Function to check if character // is operator or not static boolean isOperator(char x) { switch(x) { case '+': case '-': case '*': case '/': case '^': case '%': return true; } return false; } // Convert prefix to Infix expression public static String convert(String str) { Stack<String> stack = new Stack<>(); // Length of expression int l = str.length(); // Reading from right to left for(int i = l - 1; i >= 0; i--) { char c = str.charAt(i); if (isOperator(c)) { String op1 = stack.pop(); String op2 = stack.pop(); // Concat the operands and operator String temp = "(" + op1 + c + op2 + ")"; stack.push(temp); } else { // To make character to string stack.push(c + ""); } } return stack.pop(); } // Driver code public static void main(String[] args) { String exp = "*-A/BC-/AKL"; System.out.println("Infix : " + convert(exp)); } } // This code is contributed by abbeyme | | — |

Python3

| # Python Program to convert prefix to Infix def prefixToInfix(prefix): stack = [] # read prefix in reverse order i = len(prefix) - 1 while i >= 0: if not isOperator(prefix[i]): # symbol is operand stack.append(prefix[i]) i -= 1 else: # symbol is operator 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 # Driver code if __name__=="__main__": str = "*-A/BC-/AKL" print(prefixToInfix(str)) # This code is contributed by avishekarora | | — |

C#

| // C# program to convert prefix to Infix using System; using System.Collections; class GFG{ // Function to check if character // is operator or not static bool isOperator(char x) { switch(x) { case '+': case '-': case '*': case '/': case '^': case '%': return true; } return false; } // Convert prefix to Infix expression public static string convert(string str) { Stack stack = new Stack(); // Length of expression int l = str.Length; // Reading from right to left 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(); // Concat the operands and operator string temp = "(" + op1 + c + op2 + ")"; stack.Push(temp); } else { // To make character to string stack.Push(c + ""); } } return (string)stack.Pop(); } // Driver code public static void Main(string[] args) { string exp = "*-A/BC-/AKL"; Console.Write("Infix : " + convert(exp)); } } // This code is contributed by rutvik_56 | | — |

Javascript

| <script> // Javascript program to convert prefix to Infix // Function to check if character // is operator or not function isOperator(x) { switch(x) { case '+': case '-': case '*': case '/': case '^': case '%': return true; } return false; } // Convert prefix to Infix expression function convert(str) { let stack = []; // Length of expression let l = str.length; // Reading from right to left 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() // Concat the operands and operator let temp = "(" + op1 + c + op2 + ")"; stack.push(temp); } else { // To make character to string stack.push(c + ""); } } return stack[stack.length - 1]; } let exp = "*-A/BC-/AKL"; document.write("Infix : " + convert(exp)); // This code is contributed by suresh07. </script> | | — |

Output

Infix : ((A-(B/C))*((A/K)-L))

Time Complexity: O(n)
Auxiliary Space: O(n)

Convert Infix expression to Postfix expression

Prefix to Postfix Conversion

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

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

| // CPP Program to convert postfix to prefix #include <bits/stdc++.h> using namespace std; // function to check if character is operator or not bool isOperator(char x) { switch (x) { case '+': case '-': case '/': case '*': return true; } return false; } // Convert postfix to Prefix expression string postToPre(string post_exp) { stack<string> s; // length of expression int length = post_exp.size(); // reading from left to right for (int i = 0; i < length; i++) { // check if symbol is operator if (isOperator(post_exp[i])) { // pop two operands from stack string op1 = s.top(); s.pop(); string op2 = s.top(); s.pop(); // concat the operands and operator string temp = post_exp[i] + op2 + op1; // Push string temp back to stack s.push(temp); } // if symbol is an operand else { // push the operand to the stack s.push(string(1, post_exp[i])); } } string ans = ""; while (!s.empty()) { ans += s.top(); s.pop(); } return ans; } // Driver Code int main() { string post_exp = "ABC/-AK/L-*"; // Function call cout << "Prefix : " << postToPre(post_exp); return 0; } | | — |

Java

| // Java Program to convert postfix to prefix import java.util.*; class GFG { // function to check if character // is operator or not static boolean isOperator(char x) { switch (x) { case '+': case '-': case '/': case '*': return true; } return false; } // Convert postfix to Prefix expression static String postToPre(String post_exp) { Stack<String> s = new Stack<String>(); // length of expression int length = post_exp.length(); // reading from right to left for (int i = 0; i < length; i++) { // check if symbol is operator if (isOperator(post_exp.charAt(i))) { // pop two operands from stack String op1 = s.peek(); s.pop(); String op2 = s.peek(); s.pop(); // concat the operands and operator String temp = post_exp.charAt(i) + op2 + op1; // Push String temp back to stack s.push(temp); } // if symbol is an operand else { // push the operand to the stack s.push(post_exp.charAt(i) + ""); } } // concatenate all strings in stack and return the // answer String ans = ""; for (String i : s) ans += i; return ans; } // Driver Code public static void main(String args[]) { String post_exp = "ABC/-AK/L-*"; // Function call System.out.println("Prefix : " + postToPre(post_exp)); } } // This code is contributed by Arnab Kundu | | — |

Python3

| # Python3 Program to convert postfix to prefix # function to check if # character is operator or not def isOperator(x): if x == "+": return True if x == "-": return True if x == "/": return True if x == "*": return True return False # Convert postfix to Prefix expression def postToPre(post_exp): s = [] # length of expression length = len(post_exp) # reading from right to left for i in range(length): # check if symbol is operator if (isOperator(post_exp[i])): # pop two operands from stack op1 = s[-1] s.pop() op2 = s[-1] s.pop() # concat the operands and operator temp = post_exp[i] + op2 + op1 # Push string temp back to stack s.append(temp) # if symbol is an operand else: # push the operand to the stack s.append(post_exp[i]) ans = "" for i in s: ans += i return ans # Driver Code if __name__ == "__main__": post_exp = "AB+CD-" # Function call print("Prefix : ", postToPre(post_exp)) # This code is contributed by AnkitRai01 | | — |

C#

| // C# Program to convert postfix to prefix using System; using System.Collections; class GFG { // function to check if character // is operator or not static Boolean isOperator(char x) { switch (x) { case '+': case '-': case '/': case '*': return true; } return false; } // Convert postfix to Prefix expression static String postToPre(String post_exp) { Stack s = new Stack(); // length of expression int length = post_exp.Length; // reading from right to left for (int i = 0; i < length; i++) { // check if symbol is operator if (isOperator(post_exp[i])) { // Pop two operands from stack String op1 = (String)s.Peek(); s.Pop(); String op2 = (String)s.Peek(); s.Pop(); // concat the operands and operator String temp = post_exp[i] + op2 + op1; // Push String temp back to stack s.Push(temp); } // if symbol is an operand else { // Push the operand to the stack s.Push(post_exp[i] + ""); } } String ans = ""; while (s.Count > 0) ans += s.Pop(); return ans; } // Driver Code public static void Main(String[] args) { String post_exp = "ABC/-AK/L-*"; // Function call Console.WriteLine("Prefix : " + postToPre(post_exp)); } } // This code is contributed by Arnab Kundu | | — |

Javascript

| <script> // Javascript Program to convert postfix to prefix // function to check if character // is operator or not function isOperator(x) { switch (x) { case '+': case '-': case '/': case '*': return true; } return false; } // Convert postfix to Prefix expression function postToPre(post_exp) { let s = []; // length of expression let length = post_exp.length; // reading from right to left for (let i = 0; i < length; i++) { // check if symbol is operator if (isOperator(post_exp[i])) { // Pop two operands from stack let op1 = s[s.length - 1]; s.pop(); let op2 = s[s.length - 1]; s.pop(); // concat the operands and operator let temp = post_exp[i] + op2 + op1; // Push String temp back to stack s.push(temp); } // if symbol is an operand else { // Push the operand to the stack s.push(post_exp[i] + ""); } } let ans = ""; while (s.length > 0) ans += s.pop(); return ans; } let post_exp = "ABC/-AK/L-*"; // Function call document.write("Prefix : " + postToPre(post_exp)); // This code is contributed by suresh07. </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

Postfix to Infix

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](https://www.geeksforgeeks.org/prefix-to-postfix-converter-online/).**

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

| // CPP Program to convert prefix to postfix #include <iostream> #include <stack> using namespace std; // function to check if character is operator or not bool isOperator(char x) { switch (x) { case '+': case '-': case '/': case '*': return true; } return false; } // Convert prefix to Postfix expression string preToPost(string pre_exp) { stack<string> s; // length of expression int length = pre_exp.size(); // reading from right to left for (int i = length - 1; i >= 0; i--) { // check if symbol is operator if (isOperator(pre_exp[i])) { // pop two operands from stack string op1 = s.top(); s.pop(); string op2 = s.top(); s.pop(); // concat the operands and operator string temp = op1 + op2 + pre_exp[i]; // Push string temp back to stack s.push(temp); } // if symbol is an operand else { // push the operand to the stack s.push(string(1, pre_exp[i])); } } // stack contains only the Postfix expression return s.top(); } // Driver Code int main() { string pre_exp = "*-A/BC-/AKL"; cout << "Postfix : " << preToPost(pre_exp); return 0; } | | — |

Java

| // JavaProgram to convert prefix to postfix import java.util.*; class GFG { // function to check if character // is operator or not static boolean isOperator(char x) { switch (x) { case '+': case '-': case '/': case '*': return true; } return false; } // Convert prefix to Postfix expression static String preToPost(String pre_exp) { Stack<String> s = new Stack<String>(); // length of expression int length = pre_exp.length(); // reading from right to left for (int i = length - 1; i >= 0; i--) { // check if symbol is operator if (isOperator(pre_exp.charAt(i))) { // pop two operands from stack String op1 = s.peek(); s.pop(); String op2 = s.peek(); s.pop(); // concat the operands and operator String temp = op1 + op2 + pre_exp.charAt(i); // Push String temp back to stack s.push(temp); } // if symbol is an operand else { // push the operand to the stack s.push(pre_exp.charAt(i) + ""); } } // stack contains only the Postfix expression return s.peek(); } // Driver Code public static void main(String args[]) { String pre_exp = "*-A/BC-/AKL"; System.out.println("Postfix : " + preToPost(pre_exp)); } } // This code is contributed by Arnab Kundu | | — |

Python 3

| # Write Python3 code here # -*- coding: utf-8 -*- # Example Input s = "*-A/BC-/AKL" # Stack for storing operands stack = [] operators = set(['+', '-', '*', '/', '^']) # Reversing the order s = s[::-1] # iterating through individual tokens for i in s: # if token is operator if i in operators: # pop 2 elements from stack a = stack.pop() b = stack.pop() # concatenate them as operand1 + # operand2 + operator temp = a+b+i stack.append(temp) # else if operand else: stack.append(i) # printing final output print(*stack) | | — |

C#

| // C# Program to convert prefix to postfix using System; using System.Collections.Generic; class GFG { // function to check if character // is operator or not static bool isOperator(char x) { switch (x) { case '+': case '-': case '/': case '*': return true; } return false; } // Convert prefix to Postfix expression static String preToPost(String pre_exp) { Stack<String> s = new Stack<String>(); // length of expression int length = pre_exp.Length; // reading from right to left for (int i = length - 1; i >= 0; i--) { // check if symbol is operator if (isOperator(pre_exp[i])) { // pop two operands from stack String op1 = s.Peek(); s.Pop(); String op2 = s.Peek(); s.Pop(); // concat the operands and operator String temp = op1 + op2 + pre_exp[i]; // Push String temp back to stack s.Push(temp); } // if symbol is an operand else { // push the operand to the stack s.Push(pre_exp[i] + ""); } } // stack contains only the Postfix expression return s.Peek(); } // Driver Code public static void Main(String[] args) { String pre_exp = "*-A/BC-/AKL"; Console.WriteLine("Postfix : " + preToPost(pre_exp)); } } /* This code contributed by PrinciRaj1992 */ | | — |

Javascript

| <script> // Javascript Program to convert prefix to postfix // function to check if character // is operator or not function isOperator(x) { switch (x) { case '+': case '-': case '/': case '*': return true; } return false; } // Convert prefix to Postfix expression function preToPost(pre_exp) { let s = []; // length of expression let length = pre_exp.length; // reading from right to left for (let i = length - 1; i >= 0; i--) { // check if symbol is operator if (isOperator(pre_exp[i])) { // pop two operands from stack let op1 = s[s.length - 1]; s.pop(); let op2 = s[s.length - 1]; s.pop(); // concat the operands and operator let temp = op1 + op2 + pre_exp[i]; // Push String temp back to stack s.push(temp); } // if symbol is an operand else { // push the operand to the stack s.push(pre_exp[i] + ""); } } // stack contains only the Postfix expression return s[s.length - 1]; } let pre_exp = "*-A/BC-/AKL"; document.write("Postfix : " + preToPost(pre_exp)); // This code is contributed by suresh07. </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.

Prefix to Infix Conversion

Postfix to Prefix Conversion

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

Recommended Practice Evaluation of Postfix Expression

Try It!

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

| // C program to evaluate value of a postfix expression #include <ctype.h> #include <stdio.h> #include <stdlib.h> #include <string.h> // Stack type struct Stack { int top; unsigned capacity; int* array; }; // Stack Operations 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; } // The main function that returns value // of a given postfix expression int evaluatePostfix(char* exp) { // Create a stack of capacity equal to expression size struct Stack* stack = createStack(strlen(exp)); int i; // See if stack was created successfully if (!stack) return -1; // Scan all characters one by one for (i = 0; exp[i]; ++i) { // If the scanned character is an operand // (number here), push it to the stack. if (isdigit(exp[i])) push(stack, exp[i] - '0'); // If the scanned character is an operator, // pop two elements from stack apply the operator 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); } // Driver code int main() { char exp[] = "231*+9-"; // Function call printf("postfix evaluation: %d", evaluatePostfix(exp)); return 0; } | | — |

C++

| // C++ program to evaluate value of a postfix expression #include <bits/stdc++.h> using namespace std; // The main function that returns value // of a given postfix expression int evaluatePostfix(string exp) { // Create a stack of capacity equal to expression size stack<int> st; // Scan all characters one by one for (int i = 0; i < exp.size(); ++i) { // If the scanned character is an operand // (number here), push it to the stack. if (isdigit(exp[i])) st.push(exp[i] - '0'); // If the scanned character is an operator, // pop two elements from stack apply the operator 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(); } // Driver code int main() { string exp = "231*+9-"; // Function call cout << "postfix evaluation: " << evaluatePostfix(exp); return 0; } | | — |

Java

| // Java program to evaluate value of a postfix expression import java.util.Stack; public class Test { // Method to evaluate value of a postfix expression static int evaluatePostfix(String exp) { // Create a stack Stack<Integer> stack = new Stack<>(); // Scan all characters one by one for (int i = 0; i < exp.length(); i++) { char c = exp.charAt(i); // If the scanned character is an operand // (number here), push it to the stack. if (Character.isDigit(c)) stack.push(c - '0'); // If the scanned character is an operator, pop // two elements from stack apply the operator 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(); } // Driver code public static void main(String[] args) { String exp = "231*+9-"; // Function call System.out.println("postfix evaluation: " + evaluatePostfix(exp)); } } // Contributed by Sumit Ghosh | | — |

Python3

| # Python program to evaluate value of a postfix expression # Class to convert the expression class Evaluate: # Constructor to initialize the class variables def __init__(self, capacity): self.top = -1 self.capacity = capacity # This array is used a stack self.array = [] # Check if the stack is empty def isEmpty(self): return True if self.top == -1 else False # Return the value of the top of the stack def peek(self): return self.array[-1] # Pop the element from the stack def pop(self): if not self.isEmpty(): self.top -= 1 return self.array.pop() else: return "$" # Push the element to the stack def push(self, op): self.top += 1 self.array.append(op) # The main function that converts given infix expression # to postfix expression def evaluatePostfix(self, exp): # Iterate over the expression for conversion for i in exp: # If the scanned character is an operand # (number here) push it to the stack if i.isdigit(): self.push(i) # If the scanned character is an operator, # pop two elements from stack and apply it. else: val1 = self.pop() val2 = self.pop() self.push(str(eval(val2 + i + val1))) return int(self.pop()) # Driver code if __name__ == '__main__': exp = "231*+9-" obj = Evaluate(len(exp)) # Function call print("postfix evaluation: %d" % (obj.evaluatePostfix(exp))) # This code is contributed by Nikhil Kumar Singh(nickzuck_007) | | — |

C#

| // C# program to evaluate value of a postfix expression using System; using System.Collections; namespace GFG { class Geek { // Main() method static void Main() { Geek e = new Geek(); e.v = ("231*+9-"); e.expression(); Console.WriteLine("postfix evaluation: " + e.answer); Console.Read(); } //'v' is variable to store the string value public string v; public string answer; Stack i = new Stack(); // evaluation method 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> // Javascript program to evaluate value of a postfix expression // Method to evaluate value of a postfix expression function evaluatePostfix(exp) { //create a stack let stack=[]; // Scan all characters one by one for(let i=0;i<exp.length;i++) { let c=exp[i]; // If the scanned character is an operand (number here), // push it to the stack. if(! isNaN( parseInt(c) )) stack.push(c.charCodeAt(0) - '0'.charCodeAt(0)); // If the scanned character is an operator, pop two // elements from stack apply the operator 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(); } // Driver program to test above functions let exp="231*+9-"; document.write("postfix evaluation: "+evaluatePostfix(exp)); // This code is contributed by avanitrachhadiya2155 </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

| // C program to evaluate value of a postfix // expression having multiple digit operands #include <ctype.h> #include <stdio.h> #include <stdlib.h> #include <string.h> // Stack type struct Stack { int top; unsigned capacity; int* array; }; // Stack Operations 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; } // The main function that returns value // of a given postfix expression int evaluatePostfix(char* exp) { // Create a stack of capacity equal to expression size struct Stack* stack = createStack(strlen(exp)); int i; // See if stack was created successfully if (!stack) return -1; // Scan all characters one by one for (i = 0; exp[i]; ++i) { // if the character is blank space then continue if (exp[i] == ' ') continue; // If the scanned character is an // operand (number here),extract the full number // Push it to the stack. else if (isdigit(exp[i])) { int num = 0; // extract full number while (isdigit(exp[i])) { num = num * 10 + (int)(exp[i] - '0'); i++; } i--; // push the element in the stack push(stack, num); } // If the scanned character is an operator, pop two // elements from stack apply the operator 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); } // Driver program to test above functions int main() { char exp[] = "100 200 + 2 / 5 * 7 +"; // Function call printf("%d", evaluatePostfix(exp)); return 0; } // This code is contributed by Arnab Kundu | | — |

C++14

| // C++ program to evaluate value of a postfix // expression having multiple digit operands #include <bits/stdc++.h> using namespace std; // The main function that returns value // of a given postfix expression int evaluatePostfix(char* exp) { // Create a stack of capacity equal to expression size stack<int> st; int i; // Scan all characters one by one for (i = 0; exp[i]; ++i) { // If the character is blank space then continue if (exp[i] == ' ') continue; // If the scanned character is an // operand (number here),extract the full number // Push it to the stack. else if (isdigit(exp[i])) { int num = 0; // Extract full number while (isdigit(exp[i])) { num = num * 10 + (int)(exp[i] - '0'); i++; } i--; // Push the element in the stack st.push(num); } // If the scanned character is an operator, pop two // elements from stack apply the operator 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(); } // Driver code int main() { char exp[] = "100 200 + 2 / 5 * 7 +"; // Function call cout << evaluatePostfix(exp); return 0; } // This code is contributed by rathbhupendra | | — |

Java

| // Java program to evaluate value of a postfix // expression having multiple digit operands import java.util.Stack; class Test1 { // Method to evaluate value of a postfix expression static int evaluatePostfix(String exp) { // Create a stack Stack<Integer> stack = new Stack<>(); // Scan all characters one by one for (int i = 0; i < exp.length(); i++) { char c = exp.charAt(i); if (c == ' ') continue; // If the scanned character is an operand // (number here),extract the number // Push it to the stack. else if (Character.isDigit(c)) { int n = 0; // Extract the characters and store it in num while (Character.isDigit(c)) { n = n * 10 + (int)(c - '0'); i++; c = exp.charAt(i); } i--; // Push the number in stack stack.push(n); } // If the scanned character is an operator, pop // two elements from stack apply the operator 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(); } // Driver program to test above functions public static void main(String[] args) { String exp = "100 200 + 2 / 5 * 7 +"; // Function call System.out.println(evaluatePostfix(exp)); } } // This code is contributed by Arnab Kundu | | — |

Python3

| # Python program to evaluate value of a postfix # expression with integers containing multiple digits 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: # If the component of the list is an integer try: self.push(int(i)) # If the component of the list is not an integer, # it must be an operator. Using ValueError, we can # evaluate components of the list other than type int except ValueError: val1 = self.pop() val2 = self.pop() if i == '/': self.push(val2 / val1) else: # Switch statement to perform operation switcher = {'+': val2 + val1, '-': val2 - val1, '*': val2 * val1, '^': val2**val1} self.push(switcher.get(i)) return int(self.pop()) # Driver code if __name__ == '__main__': str = '100 200 + 2 / 5 * 7 +' # Splitting the given string to obtain # integers and operators into a list strconv = str.split(' ') obj = evalpostfix() print(obj.centralfunc(strconv)) # This code is contributed by Amarnath Reddy | | — |

C#

| // C# program to evaluate value of a postfix // expression having multiple digit operands using System; using System.Collections.Generic; class GFG { // Method to evaluate value of // a postfix expression public static int evaluatePostfix(string exp) { // Create a stack Stack<int> stack = new Stack<int>(); // Scan all characters one by one for (int i = 0; i < exp.Length; i++) { char c = exp[i]; if (c == ' ') { continue; } // If the scanned character is an // operand (number here),extract // the number. Push it to the stack. else if (char.IsDigit(c)) { int n = 0; // Extract the characters and // store it in num while (char.IsDigit(c)) { n = n * 10 + (int)(c - '0'); i++; c = exp[i]; } i--; // push the number in stack stack.Push(n); } // If the scanned character is // an operator, pop two elements // from stack apply the operator 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(); } // Driver Code public static void Main(string[] args) { string exp = "100 200 + 2 / 5 * 7 +"; // Function call Console.WriteLine(evaluatePostfix(exp)); } } // This code is contributed by Shrikant13 | | — |

Javascript

| <script> // Javascript program to evaluate value of a postfix // expression having multiple digit operands // Method to evaluate value of // a postfix expression function evaluatePostfix(exp) { // create a stack let stack = []; // Scan all characters one by one for (let i = 0; i < exp.length; i++) { let c = exp[i]; if (c == ' ') { continue; } // If the scanned character is an // operand (number here),extract // the number. Push it to the stack. else if (c >= '0' && c <= '9') { let n = 0; // extract the characters and // store it in num while (c >= '0' && c <= '9') { n = n * 10 + (c - '0'); i++; c = exp[i]; } i--; // push the number in stack stack.push(n); } // If the scanned character is // an operator, pop two elements // from stack apply the operator 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)); // This code is contributed by decode2207. </script> | | — |

Output

Time Complexity: O(N)
Auxiliary Space: O(N)

Arithmetic Expression Evaluation

How to Reverse a Stack using Recursion

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.

Tree-Traversal-Techniques-(1)

Table of Content

Tree Traversal Meaning
Tree Traversal Techniques
Inorder Traversal
Preorder Traversal
Postorder Traversal
Level Order Traversal
Other Tree Traversals
Frequently Asked Questions (FAQs) on Tree Traversal Techniques 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:

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](https://www.geeksforgeeks.org/inorder-traversal-of-binary-tree/):

Inorder traversal visits the node in the order: **Left -> Root -> Right**

Preorder-Traversal-of-Binary-Tree

**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);
}

Output

Inorder 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](https://www.geeksforgeeks.org/preorder-traversal-of-binary-tree/):

Preorder traversal visits the node in the order: **Root -> Left -> Right**

Inorder-Traversal-of-Binary-Tree

**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);
}

Output

Preorder 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](https://www.geeksforgeeks.org/postorder-traversal-of-binary-tree/):

Postorder traversal visits the node in the order: **Left -> Right -> Root**

Postorder-Traversal-of-Binary-Tree

**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 + " ");
}

Output

Postorder traversal of binary tree is 
4 5 2 3 1 

Level Order Traversal: ———————————————————————————–

**Level Order Traversal** visits all nodes present in the same level completely before visiting the next level.

Level-Order-Traversal-of-Binary-Tree

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

Level Order Traversal is mainly used as Breadth First Search to search or process nodes level-by-level.
Level Order traversal is also used for Tree Serialization and Deserialization.

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

1. Boundary 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.

2. Diagonal Traversal

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

Introduction to Tree - Data Structure and Algorithm Tutorials

Applications of tree data structure

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

Inorder Traversal:

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

| // C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Class describing a node of tree class Node { public: int data; Node* left; Node* right; Node(int v) { this->data = v; this->left = this->right = NULL; } }; // Inorder Traversal void printInorder(Node* node) { if (node == NULL) return; // Traverse left subtree printInorder(node->left); // Visit node cout << node->data << " "; // Traverse right subtree printInorder(node->right); } // Driver code int main() { // Build the tree 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); // Function call cout << "Inorder Traversal: "; printInorder(root); return 0; } | | — |

Java

| // Java code to implement the approach import java.io.*; // Class describing a node of tree class Node { int data; Node left; Node right; Node(int v) { this.data = v; this.left = this.right = null; } } class GFG { // Inorder Traversal public static void printInorder(Node node) { if (node == null) return; // Traverse left subtree printInorder(node.left); // Visit node System.out.print(node.data + " "); // Traverse right subtree printInorder(node.right); } // Driver Code public static void main(String[] args) { // Build the tree 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); // Function call System.out.print("Inorder Traversal: "); printInorder(root); } } // This code is contributed by Rohit Pradhan | | — |

Python3

| # Python3 code to implement the approach # Class describing a node of tree class Node: def __init__(self, v): self.left = None self.right = None self.data = v # Inorder Traversal def printInorder(root): if root: # Traverse left subtree printInorder(root.left) # Visit node print(root.data,end=" ") # Traverse right subtree printInorder(root.right) # Driver code if __name__ == "__main__": # Build the tree 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) # Function call print("Inorder Traversal:",end=" ") printInorder(root) # This code is contributed by ajaymakvana. | | — |

C#

| // Include namespace system using System; // Class describing a node of tree 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 { // Inorder Traversal public static void printInorder(Node node) { if (node == null) { return; } // Traverse left subtree GFG.printInorder(node.left); // Visit node Console.Write(node.data.ToString() + " "); // Traverse right subtree GFG.printInorder(node.right); } // Driver Code public static void Main(String[] args) { // Build the tree 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); // Function call Console.Write("Inorder Traversal: "); GFG.printInorder(root); } } | | — |

Javascript

| // JavaScript code to implement the approach class Node { constructor(v) { this.left = null; this.right = null; this.data = v; } } // Inorder Traversal function printInorder(root) { if (root) { // Traverse left subtree printInorder(root.left); // Visit node console.log(root.data); // Traverse right subtree printInorder(root.right); } } // Driver code if (true) { // Build the tree 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); // Function call console.log("Inorder Traversal:"); printInorder(root); } // This code is contributed by akashish__ | | — |

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

Preorder Traversal:

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

| // C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Class describing a node of tree class Node { public: int data; Node* left; Node* right; Node(int v) { this->data = v; this->left = this->right = NULL; } }; // Preorder Traversal void printPreOrder(Node* node) { if (node == NULL) return; // Visit Node cout << node->data << " "; // Traverse left subtree printPreOrder(node->left); // Traverse right subtree printPreOrder(node->right); } // Driver code int main() { // Build the tree 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); // Function call cout << "Preorder Traversal: "; printPreOrder(root); return 0; } | | — |

Java

| // Java code to implement the approach import java.io.*; // Class describing a node of tree class Node { int data; Node left; Node right; Node(int v) { this.data = v; this.left = this.right = null; } } class GFG { // Preorder Traversal public static void printPreorder(Node node) { if (node == null) return; // Visit node System.out.print(node.data + " "); // Traverse left subtree printPreorder(node.left); // Traverse right subtree printPreorder(node.right); } public static void main(String[] args) { // Build the tree 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); // Function call System.out.print("Preorder Traversal: "); printPreorder(root); } } // This code is contributed by lokeshmvs21. | | — |

Python3

| class Node: def __init__(self, v): self.data = v self.left = None self.right = None # Preorder Traversal def printPreOrder(node): if node is None: return # Visit Node print(node.data, end = " ") # Traverse left subtree printPreOrder(node.left) # Traverse right subtree printPreOrder(node.right) # Driver code if __name__ == "__main__": # Build the tree 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) # Function call print("Preorder Traversal: ", end = "") printPreOrder(root) | | — |

C#

| // Include namespace system using System; // Class describing a node of tree 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 { // Preorder Traversal public static void printPreorder(Node node) { if (node == null) { return; } // Visit node Console.Write(node.data.ToString() + " "); // Traverse left subtree GFG.printPreorder(node.left); // Traverse right subtree GFG.printPreorder(node.right); } public static void Main(String[] args) { // Build the tree 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); // Function call 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); } // Build the tree 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); // This code is contributed by akashish__ | | — |

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

Postorder Traversal:

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

| // C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Class to define structure of a node class Node { public: int data; Node* left; Node* right; Node(int v) { this->data = v; this->left = this->right = NULL; } }; // PostOrder Traversal void printPostOrder(Node* node) { if (node == NULL) return; // Traverse left subtree printPostOrder(node->left); // Traverse right subtree printPostOrder(node->right); // Visit node cout << node->data << " "; } // Driver code 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); // Function call cout << "PostOrder Traversal: "; printPostOrder(root); cout << "\n"; return 0; } | | — |

Java

| // Java code to implement the approach import java.io.*; // Class describing a node of tree class GFG { static class Node { int data; Node left; Node right; Node(int v) { this.data = v; this.left = this.right = null; } } // Preorder Traversal public static void printPreorder(Node node) { if (node == null) return; // Traverse left subtree printPreorder(node.left); // Traverse right subtree printPreorder(node.right); // Visit node System.out.print(node.data + " "); } public static void main(String[] args) { // Build the tree 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); // Function call System.out.print("Preorder Traversal: "); printPreorder(root); } } | | — |

C#

| // Include namespace system using System; // Class describing a node of tree 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 { // Preorder Traversal public static void printPreorder(Node node) { if (node == null) { return; } // Traverse left subtree GFG.printPreorder(node.left); // Traverse right subtree GFG.printPreorder(node.right); // Visit node Console.Write(node.data.ToString() + " "); } public static void Main(String[] args) { // Build the tree 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); // Function call Console.Write("Preorder Traversal: "); GFG.printPreorder(root); } } | | — |

Python3

| class Node: def __init__(self, v): self.data = v self.left = None self.right = None # Preorder Traversal def printPostOrder(node): if node is None: return # Traverse left subtree printPostOrder(node.left) # Traverse right subtree printPostOrder(node.right) # Visit Node print(node.data, end = " ") # Driver code if __name__ == "__main__": # Build the tree 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) # Function call print("Postorder Traversal: ", end = "") printPostOrder(root) | | — |

Javascript

| class Node { constructor(v) { this.data = v; this.left = null; this.right = null; } } // Preorder Traversal function printPostOrder(node) { if (node === null) { return; } // Traverse left subtree printPostOrder(node.left); // Traverse right subtree printPostOrder(node.right); // Visit Node console.log(node.data, end = " "); } // Driver code // Build the tree 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); // Function call console.log("Postorder Traversal: ", end = ""); printPostOrder(root); // This code is contributed by akashish__ | | — |

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

Deletion in Binary Search Tree (BST)

Balance a Binary Search Tree

Infix, Postfix and Prefix Expressions/Notations

Infix Expressions

Common way of writing Infix expressions:

Operator precedence rules:

Evaluating Infix Expressions

Advantages of Infix Expressions

Disadvantages Infix Expressions

Prefix Expressions (Polish Notation)

Evaluating Prefix Expressions

Advantages of Prefix Expressions

Disadvantages of Prefix Expressions

Postfix Expressions (Reverse Polish Notation)

Evaluating Postfix Expressions (Reverse Polish Notation)

Advantages of Postfix Notation

Disadvantages of Postfix Expressions

Comparison of Infix, Prefix and Postfix Expressions

Frequently Asked Questions on Infix, Postfix and Prefix Expressions

1. What is an infix expression?

2. What is a postfix expression?

3. What is a prefix expression?

4. How are infix expressions evaluated?

5. How are postfix expressions evaluated?

6. How are prefix expressions evaluated?

7. What are the advantages of postfix and prefix expressions over infix expressions?

8. Can infix expressions be converted to postfix or prefix expressions?

9. Are postfix and prefix expressions more efficient than infix expressions in terms of evaluation?

10. When should I use infix, postfix, or prefix expressions in my programming code?

**Why postfix representation of the expression?**

How to convert an Infix expression to a Postfix expression?

**Illustration:**

C++14

C

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

**Algorithm for Prefix to Postfix**:

C++

Java

Python 3

C#

Javascript

Evaluation of Postfix Expression using Stack:

C

C++

Java

Python3

C#

Javascript

There are the following limitations of the above implementation.

Postfix evaluation for multi-digit numbers:

C

C++14

Java

Python3

C#

Javascript

Tree Traversal Techniques:

[**Inorder Traversal](https://www.geeksforgeeks.org/inorder-traversal-of-binary-tree/):**

[**Preorder Traversal](https://www.geeksforgeeks.org/preorder-traversal-of-binary-tree/):**

[**Postorder Traversal](https://www.geeksforgeeks.org/postorder-traversal-of-binary-tree/):**

Other Tree Traversals:

1. Boundary Traversal:

2. Diagonal Traversal

Frequently Asked Questions (FAQs) on Tree Traversal Techniques:

**1. What are tree traversal techniques?**

**2. What are the common types of tree traversal?**

**3. What is Inorder traversal?**

**4. What is preorder traversal?**

**5. What is postorder traversal?**

Why postfix representation of the expression?

Illustration:

Algorithm for Prefix to Postfix:

[Inorder Traversal](https://www.geeksforgeeks.org/inorder-traversal-of-binary-tree/):

[Preorder Traversal](https://www.geeksforgeeks.org/preorder-traversal-of-binary-tree/):

[Postorder Traversal](https://www.geeksforgeeks.org/postorder-traversal-of-binary-tree/):

1. What are tree traversal techniques?

2. What are the common types of tree traversal?

3. What is Inorder traversal?

4. What is preorder traversal?

5. What is postorder traversal?

6. What is level order traversal?

7. When should I use each traversal technique?

8. How do I implement tree traversal algorithms?

9. Can tree traversal algorithms be applied to other tree-like structures?

10. Are there any performance considerations when choosing a traversal technique?