EDUCBA

EDUCBA

MENUMENU
  • Free Tutorials
  • Free Courses
  • Certification Courses
  • 360+ Courses All in One Bundle
  • Login
Home Data Science Data Science Tutorials Data Structures Tutorial Inorder Traversal of Binary Tree
Secondary Sidebar
Data Structures Tutorial
  • Basics
    • Linked List Advantages
    • What is Data Structure
    • Heap Data Structure
    • Types of Trees in Data Structure
    • AVL Tree in Data Structure
    • B Tree in Data Structure
    • B+ Tree in Data Structure
    • DFS Algorithm
    • BFS Algorithm
    • Arrays in Data Structure
    • Graph in Data Structure
    • Graph Representation
    • Breadth First Search
    • Depth Limited Search
    • Hashing in Data Structure
    • Searching in Data Structure
    • Linear Search in Data Structure
    • Linked List in Data Structure
    • Doubly linked list in Data Structure
    • Circular Linked List in Data Structure
    • Pointers in Data Structure
    • Types of Graph in Data Structure
    • Bubble Sort in Data Structure
    • Quick Sort in Data Structure
    • Bitonic Sort
    • Merge Sort in Data Structure
    • Selection Sort in Data Structure
    • Insertion Sort in Data Structure
    • Radix Sort in Data Structure
    • Stack in Data Structure
    • Queue in Data Structure
    • Priority Queue in Data Structure
    • Asymptotic Analysis
    • Tree Traversal in Data Structure
    • Tree Traversal Techniques
    • Trie Data Structure
    • Splay Tree in Data Structure
    • Spanning Tree Algorithm
    • Sparse Matrix in Data Structure
    • Radix Sort Algorithm
    • Counting Sort Algorithm
    • Skip List Data Structure
    • Linked List Algorithm
    • Linked List Types
    • Inorder Traversal of Binary Tree
    • Kruskals Algorithm
    • Prims Algorithm
    • BFS VS DFS
    • BCNF
    • Skip List
    • Hash Table?in Data Structure
    • Data Structure Interview Questions
    • Data Structures & Algorithms Interview
    • AVL Tree Deletion
    • B+ Tree Deletion
    • Decision Tree Advantages and Disadvantages
    • Data Architect Skills
    • Data Architecture Principles
    • Data Engineer Jobs
    • Data Engineer Roadmap
    • Fundamentals of Data Structure
    • Circular queue in Data Structure
    • Spanning Tree in Data Structure
    • Tree traversal types
    • Deque in Data structure
    • Shell Sort in Data Structure
    • Heap sort in data structure
    • Heap data structure C++
    • Heap data structure in Java
    • Binary Search Tree Types
    • Binary Tree in Data Structure
    • Binary Tree Types
    • Binary search tree in data structure
    • Binary Search Tree Advantages
    • Binary Search Tree Properties
    • Binary Search in Data Structure
    • Binary Tree Deletion
    • Sparse Matrix Multiplication
    • Preorder Traversal of Binary Tree
    • Postorder traversal
    • Decision Tree Hyperparameters
    • PostOrder Traversal without Recursion
    • AVL Tree Rotation
    • Avro File Format
    • Decision Tree Types
    • Binomial heap
    • Confluence Jira Integration
    • Timm Sort
    • Depth First Search

Related Courses

All in One Data Science Course

Oracle DBA Course

SQL Certification Course

Inorder Traversal of Binary Tree

Inorder Traversal of Binary Tree

Introduction to Inorder Traversal of Binary Tree

In a binary tree, there are many operations we can perform, one of the main operations is traversing the tree. The process of getting, modifying, checking the data of all nodes in a tree is called Tree Traversal. Using Tree traversal, we can get the data of all nodes or update, search any node. As we know, in linear data structures like arrays, linked lists, stacks we perform sequentially traversing. But, the binary trees can be traversed in many different ways.
A sequence of processing of all nodes in a binary tree differentiates the traversing binary tree type. The main classification is based on the order of root node, left subtree or left child node, and right child node.

There are mainly three types of traversing:

a. Inorder Traversal
b. Preorder Traversal
c. Postorder Traversal

Inorder Traversal of Binary Tree 1

Start Your Free Data Science Course

Hadoop, Data Science, Statistics & others

Syntax:

1. In Inorder traversal, traversal starts from the leftmost node of the binary tree and ends with a rightmost node of a binary tree. The root node in Inorder traversal always calls between the left subtree and right subtree. There are two ways to perform Inorder traversal:

2. Recursive approach

In the recursive approach, start from the root node, the first call recursively left child node until we get NULL then get the current data, and then call right subtree until we get NULL.

3. Iterative approach

In the iterative approach, create a stack and push the nodes until we find NULL in the left child then pop in the stack accordingly.

How Inorder traversal of binary tree works?

  • Inorder traversing is one of the traversing techniques to get all nodes of a binary tree, In inorder traversing, the left subtree is processed before the current node and the right subtree is after the current node.
  • To perform Inorder traversing, traverse left subtree until getting leftmost node. Then visit the root node, then traverse the right subtree of every node.
  • In the recursive approach, the traversal node stores in the stack memory of the machine whereas in the iterative approach stack data structure is used for storing the traversal node.

Now Let’s understand both approaches with an example.

Examples

Let us take the below binary tree and traverse all nodes in Inorder traversing using recursive and iterative methods.

number

1. Recursive approach

In the recursive approach as we discuss above, the first call recursively left child node until getting NULL value then get node value and then call recursively right child node until getting NULL. So now print the value of all nodes inorder traversing.

Step 1. Construct a binary tree as above using the GenerateBTNode function.
Step 2. Call displayTreeInorder and pass the root node.
Step 3. First, call displayTreeInorder and pass the left child of the current node recursively until we get NULL.
Step 4. After that print the value of the current node.
Step 5. Call the same displayTreeInorder and pass the right child of the current node recursively until we get NULL.
Step 6. When all recursive functions are complete, inorder traversal of binary tree is complete.

struct BTNode
{
int value; // element value
struct BTNode * left; // To store address of left child
struct BTNode * right; // To store address of right child
};
struct BTNode *GenerateBTNode (int data) {
struct BTNode *node = new BTNode;
node->value = data;
node->right = NULL;
node->left = NULL;
return node;
}
void displayTreeInorder (struct BTNode *root) {
if(root != NULL) {
displayTreeInorder(root->left);
cout << root->value << " ";
displayTreeInorder(root->right);
}
}
int main() {
BTNode *root = NULL;
root = GenerateBTNode(5);
root->left = GenerateBTNode(7);
root->right = GenerateBTNode(8);
root->left->left = GenerateBTNode(12);
root->left->right = GenerateBTNode(4);
root->right->left = GenerateBTNode(15);
root->right->right = GenerateBTNode(20);
displayTreeInorder(root);
}

Output:

Inorder Traversal of Binary Tree 2

2. Iterative approach

In iterative approach, the stack data structure is used. We need to store the current or parent node so that after processing the left subtree we can process the node so we push the node in the stack data structure. After processing the node, we pop that respective node.

Step 1. Construct a binary tree as above using GenerateBTNode function.

Step 2. Call displayTreeInorderIterative function and pass the root node.

Step 3. Create dummy node as temp and initially set temp as root.

All in One Data Science Bundle(360+ Courses, 50+ projects)
Python TutorialMachine LearningAWSArtificial Intelligence
TableauR ProgrammingPowerBIDeep Learning
Price
View Courses
360+ Online Courses | 50+ projects | 1500+ Hours | Verifiable Certificates | Lifetime Access
4.7 (86,241 ratings)

Step 4. Create stack of BTNode type.

Step 5. Push the temp node and update the temp node to the left child of the node.

Step 6. Do step 5 until we get NULL.

Step 7. If we reached NULL, then it means that we reached leftmost node of a tree.

Step 8. Then we simply print the value of the node and update temp to the right child of node and pop the stack and do step 5 again.

Step 9. When stack is empty and temp node is NULL then we completely traversed the binary tree.

struct BTNode
{
int value; // element value
struct BTNode * left; //To store address of left child
struct BTNode * right; //To store address of right child
};
struct BTNode *GenerateBTNode(int data) {
struct BTNode *node = new BTNode;
node->value = data;
node->right = NULL;
node->left = NULL;
return node;
}
void displayTreeInorderIterative (struct BTNode *root) {
stack <BTNode* > S;
BTNode *temp = root;
while (temp != NULL || !S.empty() ) {
if( temp != NULL) {
S.push(temp);
temp = temp->left;
}
else {
temp = S.top();
S.pop();
cout << temp->value << " ";
temp = temp->right;
}
}
}
int main() {
BTNode *root = NULL;
root = GenerateBTNode(5);
root->left = GenerateBTNode(7);
root->right = GenerateBTNode(8);
root->left->left = GenerateBTNode(12);
root->left->right = GenerateBTNode(4);
root->right->left = GenerateBTNode(15);
root->right->right = GenerateBTNode(20);
displayTreeInorderIterative(root);
}

Output:

Inorder Traversal of Binary Tree 3

Conclusion

Inorder traversing is based on Depth First Search(DFS) algorithm. There is another traversing also based on Breadth-First Search(BFS) is called Level Order traversing. In Binary Search Tree, inorder traversal gives the sorted list of all nodes. The Time Complexity of Inorder traversal is O(N).

Recommended Articles

This is a guide to Inorder Traversal of Binary Tree. Here we discuss the definition, syntax, How work Inorder traversal of binary tree? examples with code implementation. You may also have a look at the following articles to learn more –

  1. B Tree in Data Structure
  2. B+ Tree in Data Structure
  3. Decision Tree in Data Mining
  4. Create Decision Tree
Popular Course in this category
Data Scientist Training (85 Courses, 67+ Projects)
  85 Online Courses |  67 Hands-on Projects |  660+ Hours |  Verifiable Certificate of Completion
4.8
Price

View Course

Related Courses

All in One Data Science Bundle (360+ Courses, 50+ projects)4.9
Oracle DBA Database Management System Training (2 Courses)4.8
SQL Training Program (7 Courses, 8+ Projects)4.7
0 Shares
Share
Tweet
Share
Primary Sidebar
Footer
About Us
  • Blog
  • Who is EDUCBA?
  • Sign Up
  • Live Classes
  • Corporate Training
  • Certificate from Top Institutions
  • Contact Us
  • Verifiable Certificate
  • Reviews
  • Terms and Conditions
  • Privacy Policy
  •  
Apps
  • iPhone & iPad
  • Android
Resources
  • Free Courses
  • Database Management
  • Machine Learning
  • All Tutorials
Certification Courses
  • All Courses
  • Data Science Course - All in One Bundle
  • Machine Learning Course
  • Hadoop Certification Training
  • Cloud Computing Training Course
  • R Programming Course
  • AWS Training Course
  • SAS Training Course

ISO 10004:2018 & ISO 9001:2015 Certified

© 2022 - EDUCBA. ALL RIGHTS RESERVED. THE CERTIFICATION NAMES ARE THE TRADEMARKS OF THEIR RESPECTIVE OWNERS.

EDUCBA
Free Data Science Course

SPSS, Data visualization with Python, Matplotlib Library, Seaborn Package

*Please provide your correct email id. Login details for this Free course will be emailed to you

By signing up, you agree to our Terms of Use and Privacy Policy.

EDUCBA Login

Forgot Password?

By signing up, you agree to our Terms of Use and Privacy Policy.

EDUCBA
Free Data Science Course

Hadoop, Data Science, Statistics & others

*Please provide your correct email id. Login details for this Free course will be emailed to you

By signing up, you agree to our Terms of Use and Privacy Policy.

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you

By signing up, you agree to our Terms of Use and Privacy Policy.

Let’s Get Started

By signing up, you agree to our Terms of Use and Privacy Policy.

This website or its third-party tools use cookies, which are necessary to its functioning and required to achieve the purposes illustrated in the cookie policy. By closing this banner, scrolling this page, clicking a link or continuing to browse otherwise, you agree to our Privacy Policy

Loading . . .
Quiz
Question:

Answer:

Quiz Result
Total QuestionsCorrect AnswersWrong AnswersPercentage

Explore 1000+ varieties of Mock tests View more