Data Structures Tutorial

Data Structures Tutorial Asymptotic Notation Structure and Union Array Data Structure Linked list Data Structure Type of Linked list Advantages and Disadvantages of linked list Queue Data Structure Implementation of Queue Stack Data Structure Implementation of Stack Sorting Insertion sort Quick sort Selection sort Heap sort Merge sort Bucket sort Count sort Radix sort Shell sort Tree Traversal of the binary tree Binary search tree Graph Spanning tree Linear Search Binary Search Hashing Collision Resolution Techniques

Misc Topic:

Priority Queue in Data Structure Deque in Data Structure Difference Between Linear And Non Linear Data Structures Queue Operations In Data Structure About Data Structures Data Structures Algorithms Types of Data Structures Big O Notations Introduction to Arrays Introduction to 1D-Arrays Operations on 1D-Arrays Introduction to 2D-Arrays Operations on 2D-Arrays Strings in Data Structures String Operations Application of 2D array Bubble Sort Insertion Sort Sorting Algorithms What is DFS Algorithm What Is Graph Data Structure What is the difference between Tree and Graph What is the difference between DFS and BFS Bucket Sort Dijkstra’s vs Bellman-Ford Algorithm Linear Queue Data Structure in C Stack Using Array Stack Using Linked List Recursion in Fibonacci Stack vs Array What is Skewed Binary Tree Primitive Data Structure in C Dynamic memory allocation of structure in C Application of Stack in Data Structures Binary Tree in Data Structures Heap Data Structure Recursion - Factorial and Fibonacci What is B tree what is B+ tree Huffman tree in Data Structures Insertion Sort vs Bubble Sort Adding one to the number represented an array of digits Bitwise Operators and their Important Tricks Blowfish algorithm Bubble Sort vs Selection Sort Hashing and its Applications Heap Sort vs Merge Sort Insertion Sort vs Selection Sort Merge Conflicts and ways to handle them Difference between Stack and Queue AVL tree in data structure c++ Bubble sort algorithm using Javascript Buffer overflow attack with examples Find out the area between two concentric circles Lowest common ancestor in a binary search tree Number of visible boxes putting one inside another Program to calculate the area of the circumcircle of an equilateral triangle Red-black Tree in Data Structures Strictly binary tree in Data Structures 2-3 Trees and Basic Operations on them Asynchronous advantage actor-critic (A3C) Algorithm Bubble Sort vs Heap Sort Digital Search Tree in Data Structures Minimum Spanning Tree Permutation Sort or Bogo Sort Quick Sort vs Merge Sort Boruvkas algorithm Bubble Sort vs Quick Sort Common Operations on various Data Structures Detect and Remove Loop in a Linked List How to Start Learning DSA Print kth least significant bit number Why is Binary Heap Preferred over BST for Priority Queue Bin Packing Problem Binary Tree Inorder Traversal Burning binary tree Equal Sum What is a Threaded Binary Tree? What is a full Binary Tree? Bubble Sort vs Merge Sort B+ Tree Program in Q language Deletion Operation from A B Tree Deletion Operation of the binary search tree in C++ language Does Overloading Work with Inheritance Balanced Binary Tree Binary tree deletion Binary tree insertion Cocktail Sort Comb Sort FIFO approach Operations of B Tree in C++ Language Recaman’s Sequence Tim Sort Understanding Data Processing Applications of trees in data structures Binary Tree Implementation Using Arrays Convert a Binary Tree into a Binary Search Tree Create a binary search tree Horizontal and Vertical Scaling Invert binary tree LCA of binary tree Linked List Representation of Binary Tree Optimal binary search tree in DSA Serialize and Deserialize a Binary Tree Tree terminology in Data structures Vertical Order Traversal of Binary Tree What is a Height-Balanced Tree in Data Structure Convert binary tree to a doubly linked list Fundamental of Algorithms Introduction and Implementation of Bloom Filter Optimal binary search tree using dynamic programming Right side view of binary tree Symmetric binary tree Trim a binary search tree What is a Sparse Matrix in Data Structure What is a Tree in Terms of a Graph What is the Use of Segment Trees in Data Structure What Should We Learn First Trees or Graphs in Data Structures All About Minimum Cost Spanning Trees in Data Structure Convert Binary Tree into a Threaded Binary Tree Difference between Structured and Object-Oriented Analysis FLEX (Fast Lexical Analyzer Generator) Object-Oriented Analysis and Design Sum of Nodes in a Binary Tree What are the types of Trees in Data Structure What is a 2-3 Tree in Data Structure What is a Spanning Tree in Data Structure What is an AVL Tree in Data Structure Given a Binary Tree, Check if it's balanced

Binary Tree Inorder Traversal

The binary tree is a type of tree in which each and every node has atleast two children except the leaf nodes. We have various operations in the binary tree, and all of them have their own functions as well as implementations. These operations are insertion, deletion, traversal and many more. In this article, we are briefly going to discuss the various different methods of traversal. The traversal operation has many of its own approaches that are inorder, postorder and preorder traversal.

Inorder traversal

When we have a binary tree, and we want to explore and traverse that tree in ascending order, then we usually use this kind of approach, which is the inorder traversal. When we talk about linear data structures, which are linked lists, arrays, stacks, and queues, in those data structures we can only explore or traverse in one direction. Still, in non-linear data structures, such as the tree and graphs, there are several different ways in which we can traverse or explore the data. Here, we will discuss another way of traversing the data structure, which is the inorder traversal.

The inorder traversal method generally hovers over the basic principle of left root right policy. In this policy, the left root right implies that the left subtree of the current root node is visited first; when we start traversing, we visit the root node, then we commute to the right subtree, and its root node is visited. Here, the name itself suggests that the traversal or exploration occurs between the left and right subtrees.

Mainly there are two given approaches or ways in which we can simply use for the traversal in the tree. They are: -

  1. Inorder traversal using recursion
  2. Inorder traversal using an iterative method

Now we will describe each of them in detail: -

Inorder traversal using recursion

In this type of inorder traversal, we first have to process and configure all the given nodes in the left subtree, and then we have to store and keep them intact in the root node. After that, when we have processed and configured all the nodes present in the right subtree.

Inorder traversal using an iterative method

The iterative traversal of the tree is done by using the stack data structure and is one of the best methods to traverse a tree. We first have to initialize the stack and then push the current node onto the stack.

Algorithm for ignored traversal

  1. In this, firstly, we have to visit all the nodes and vertices that are situated in the left subtree.
  2. Then we have to commute to the root node.
  3. After finishing that, we will visit all the nodes that are present in the right subtree.
inorder(root->left)
display(root->data)
inorder(root->right)

Implementation of inorder traversal using recursive method

#include <iostream>
using namespace std;
struct Node
{
    int data;
    Node *lft, *rt;
 
    Node(int info)
    {
        this->info = info;
        this->lft = this->rt = nullpointr;
    }
};
 
// We will use a recursive function to perform the mechanism of inorder traversal on the tree. 
void inorder(Nod* root)
{
    // return if found out the current node is clear and 
    if (root == nullpointr) {
        return;
    }
 
    // We have to travel to the left subtree 
    inorder(root->lft);
 
    //We will next showcase the information part of the root(or current node). 
    cout << root->info << " ";
 
    // We have to travel to the right subtree 
    inorder(root->rt);
}
 
int main()
{
    /* Build the following tree
               1
             /   \
            /     \
           2       3
          /      /   \
         /      /     \
        4      5       6
              / \
             /   \
            7     8
    */
 
    Nod* root = new Nod(1);
    root->lft = new Nod(2);
    root->rt = new Nod(3);
    root->lft->lft = new Nod(4);
    root->rt->lft = new Nod(5);
    root->rt->rt = new Nod(6);
    root->rt->lft->lft = new Nod(7);
    root->rt->lft->rt = new Nod(8);
 
    inorder(root);
 
    return 0;
}

Output:

BINARY TREE INORDER TRAVERSAL

Implementation of inorder traversal using the iterative method

#include <iostream>
#include <stack>
using namespace std;
 struct Node
{
    int info;
    Nod *lft, *rt;
 
    Nod(int info)
    {
        this->info = info;
        this->lft = this->rt = nullpointr;
    }
};
 
// We will use an Iterative function to perform the mechanism of inorder traversal on the tree. 
 void inorderIterative(Nod* root)
{
    // We will first have to create a vacant stack which is completely empty
    stack<Nod*> stack;
 
    // We have to begin from the root node and then initialize the current node to the root node 
    Nod* current = root;
 
    // By any chance, if the current node which is provided to us is zero and the stack is also vacant, then we are done
    while (!stack.empty() || current!= nullpointr)
    {
        // when we find the current node, occupy it and press it back into the given stack and then shift it to the left node.
        if (current!= nullpointr)
        {
            stack.push(current);
            current = current->lft;
        }
        else {
            // In case the current node that we have is empty; then we have to pop an element from the allotted stack. 
            // Set it to print the result
            current = stack.top();
            stack.pop();
            cout << current->info << " ";
 
            curr = current->rt;
        }
    }
}
 
int main()
{
    /* Build the following tree
               1
             /   \
            /     \
           2       3
          /      /   \
         /      /     \
        4      5       6
              / \
             /   \
            7     8
    */
 
    Nod* root = new Nod(1);
    root->lft = new Nod(2);
    root->rt = new Nod(3);
    root->lft->lft = new Nod(4);
    root->rt->lft = new Nod(5);
    root->rt->rt = new Nod(6);
    root->rt->lt->lt = new Nod(7);
    root->rt->lft->rt = new Nod(8);
 
    inorderIterative(root);
 
    return 0;
}

Output:

BINARY TREE INORDER TRAVERSAL



ADVERTISEMENT
ADVERTISEMENT