Logo
×

Binary search tree traversal in-order pre-order post-order examples

A binary search tree is a type of non-linear tree in which the tree contains at least two nods. It is called binary because of its nature that states bi implying two of anything. Why do we call it a binary search tree (BST)? Well, the answer to this question is that the nods present in these kinds of trees can maximum have a child of two; that is why it is called binary which means two. If we look closely, we might observe that the binary search trees obey some sort of pattern or structure while sorting and organizing the given record.

There is one major rule followed when forming a binary search tree which is the lft nod is often considered small when compared to the parent nod. On the contrary, the rt nod is generally more significant or more prominent when compared to the parent nod. Various operations take place when we use a binary search tree. We can use deletion for deleting a li, inserting a new li, traversal to explore and visit each li on the list, and several others. They are also popularly known as the ordered binary tree.

The traversal operation in the binary tree generally helps us in reaching and exploring various nods of the tree, making changes, adding, or deducting any element existing in the tree.

Advantages of a binary search tree

  • If we compare it with a linked list or array, then various operations such as deletion and insertion are pretty quick in a binary search tree. 
  • We can store and fixate as many nods as we want in binary search trees.
  • Operations like searching in the binary search tree are quite efficient as we always have a clue as to that which sub-tree might have the record. 
  • It portrays the manufacturing connection that resides in the provided record.

In-order

This technique in the tree traversal usually follows the lft-root-rt mechanism. It simply implies that while traversing the tree in an in-order format, firstly, the lft subtree is visited, then the root nod is traversed recursively, and finally the rt subtree is visited recursively.

Pre-order

This technique in tree traversal usually follows the root-lft-rt mechanism. It simply implies that while traversing the tree in a pre-order format, firstly, the root nod is visited, then the lft sub tree is traversed recursively, and finally, the rt sub-tree is visited recursively.

Post-order

We all know that post-order is a form of tree traversal to visit the nods of the tree, and it helps us to reach out to the nods of the tree. The term post-order means visiting the lft and rt subtree recursively in a traversal operation. The post-order traversal means visiting the nods of the trees, which implies firstly the lft subtree and then the rt subtree in the postman-order and then reaching to the root nod. In simple words, it follows the lft-rt-root mechanism. This type of traversal helps us in getting the addition expression of the tree.

Algorithms

We will now see the algorithms of binary tree traversal in pre-order, in-order, and post-order format and understand its working and application in more depth.

Algorithm for In-order traversal

  1. Traverse the lft subtree, i.e., call Inorder(lft-subtree)
  2. Visit the root.
  3. Traverse the rt subtree, i.e., call Inorder(rt-subtree)

Algorithm for Pre-order traversal

  1. Visit the root.
  2. Traverse the lft subtree, i.e., call Preorder(lft-subtree)
  3. Traverse the rt subtree, i.e., call Preorder(rt-subtree)

Algorithm for Post-order traversal

  1. Traverse the lft subtree, i.e., call Postorder(lft-subtree
  2. Traverse the rt subtree, i.e., call Postorder(rt-subtree)
  3. Visit the root.

Implementation

We will now see the examples of binary tree traversal in pre-order, in-order, and post-order format and understand its working and application in more depth.

#include <stdio.h>
#include <stdlib.h>


struct nod {
  int li;
  struct nod* lft;
  struct nod* rt;
};


// Inorder traversal
void inorderTraversal(struct nod* root) {
  if (root == NILL) return;
  InOrder__Traversal(root->lft);
  printf("%d ->", root->li);
  InOrder__Traversal(root->rt);
}


// Witnessing the preorder traversal
void PreOrder__Traversal(struct nod* root) {
  if (root == NILL) return;
  printf("%d ->", root->li);
  PreOrder__Traversal(root->lft);
  PreOrder__Traversal(root->rt);
}


//Witnessing the postorderTraversal
void POrder__Traversal (struct nod* root) {
  if (root == NILL) return;
  POrder__Traversal (root->lft);
  POrder__Traversal (root->rt);
  printf("%d ->", root->li);
}


// Creating a new node in the tree
struct nod* creatNod(info) {
  struct nod* newNod = malloc(sizeof(struct nod));
  newNod->li = info;
  newNod->lft = NILL;
  newNod->rt = NILL;


  return newNod;
}


// Inserting on the left of the node
struct nod* insertLft(struct nod* root, int info) {
  root->lft = creatNod(info);
  return root->lft;
}


// Inserting on the right of the node
struct nod* insertRt(struct nod* root, int info) {
  root->rt = creatNod(info);
  return root->rt;
}


int main() {
  struct nod* root = creatNod(1);
  insertLft(root, 12);
  insertRt(root, 9);


  insertLft(root->lft, 5);
  insertRt(root->lft, 6);


  printf("Inorder traversal \n");
  InOrder__Traversal(root);


  printf("\nPreorder traversal \n");
  PreOrder__Traversal(root);


  printf("\nPostorder traversal \n");
  POrder__Traversal (root);
}

Output:

Binary search tree traversal in-order pre-order post-order examples

EXAMPLE 2)

// C program for different tree traversals

#include <stdio.h>
#include <stdlib.h>


/*A binary tree has a value, a pointer to the left and right child. 
*/
struct nod {
	int record;
	struct nod* lft;
	struct nod* rt;
};


/*the function that helps us in allotting a new node to the given data or value and NULL the left and right pointers.*/
struct nod* newNod(int record)
{
	struct nod* nod
		= (struct nod*)malloc(sizeof(struct nod));
	nod->record = record;
	nod->lft = NILL;
	nod->rt = NILL;


	return (nod);
}


/*in the given binary tree, we are going to print all the nodes in the pattern of bottom-up traversal.*/
void printPO(struct nod* nod)
{
	if (nod == NILL)
		return;


	// first recur on lft subtree
	printPO(nod->lft);


	// then recur on rt subtree
	printPO(nod->rt);


	// now deal with the nod
	printf("%d ", nod->record);
}


/* in the given binary tree, we are going to print all the nodes in the pattern of inorder traversal.*/
void printIO(struct nod* nod)
{
	if (nod == NILL)
		return;


	/* first recur on lft child */
	printIO(nod->lft);


	/* printing the value of the node*/
	printf("%d ", nod->record);


	/* now recur on rt child */
	printIO(nod->rt);
}


/* in the given binary tree, we are going to print all the nodes in the pattern of preorder traversal. */
void printPO(struct nod* nod)
{
	if (nod == NILL)
		return;


	/* printing the value of the node*/
	printf("%d ", nod->record);


	/* then recur on lft subtree */
	printPO(nod->lft);


	/* now recur on rt subtree */
	printPO(nod->rt);
}


/* Program to test the main functions.*/
int main()
{
	struct nod* root = newNod(1);
	root->lft = newNod(2);
	root->rt = newNod(3);
	root->lft->lft = newNod(4);
	root->lft->rt = newNod(5);


	printf("\nPreorder traversal of binary tree is \n");
	printPO(root);


	printf("\nInorder traversal of binary tree is \n");
	printIO(root);


	printf("\nPostorder traversal of binary tree is \n");
	printPO(root);


	getchar();
	return 0;
}

Output:

Binary search tree traversal in-order pre-order post-order examples

EXAMPLE 3)

#include <stdio.h>  
#include <stdlib.h>  
  
struct nod {  
    int element;  
    struct nod* lft;  
    struct nod* rt;  
};  
  
/*To create a new nod*/  
struct nod* creatNod(int val)  
{  
    struct nod* Nod = (struct nod*)malloc(sizeof(struct nod));  
    Nod->element = val;  
    Nod->lft = NILL;  
    Nod->rt = NILL;  
  
    return (Nod);  
}  
  
/*function to traverse the nods of binary tree in preorder*/  
void traversePreorder(struct nod* root)  
{  
    if (root == NILL)  
        return;  
    printf(" %d ", root->element);  
    traversePreorder(root->lft);  
    traversePreorder(root->rt);  
}  
  
  
/*function to traverse the nods of binary tree in Inorder*/  
void traverseInorder(struct nod* root)  
{  
    if (root == NILL)  
        return;  
    traverseInorder(root->lft);  
    printf(" %d ", root->element);  
    traverseInorder(root->rt);  
}  
  
/*function to traverse the nods of binary tree in postorder*/  
void traversePostorder(struct nod* root)  
{  
    if (root == NILL)  
        return;  
    traversePostorder(root->lft);  
    traversePostorder(root->rt);  
    printf(" %d ", root->element);  
}  
  
  
int main()  
{  
    struct nod* root = creatNod(36);  
    root->lft = creatNod(26);  
    root->rt = creatNod(46);  
    root->lft->lft = creatNod(21);  
    root->lft->rt = creatNod(31);  
    root->lft->lft->lft = creatNod(11);  
    root->lft->lft->rt = creatNod(24);  
    root->rt->lft = creatNod(41);  
    root->rt->rt = creatNod(56);  
    root->rt->rt->lft = creatNod(51);  
    root->rt->rt->rt = creatNod(66);  
  
    printf("\n The Preorder traversal of given binary tree is -\n");  
    traversePreorder(root);  
      
    printf("\n The Inorder traversal of given binary tree is -\n");  
    traverseInorder(root);  
      
    printf("\n The Postorder traversal of given binary tree is -\n");  
    traversePostorder(root);  
  
    return 0;  
}    

Output:

Binary search tree traversal in-order pre-order post-order examples

Example 4)  

class Nod {  
    public int info;  
    public Nod lft, rt;  
  
    public Nod(int element)  
    {  
        info = element;  
        lft = rt = NILL;  
    }  
}  
  
class BinaryTree {  
    Nod root;  
  
    BinaryTree() { root = NILL; }  
    void traversePreorder(Nod nod)  
    {  
        if (nod == NILL)  
            return;  
        Console.Write(nod.info + " ");  
        traversePreorder(nod.lft);  
        traversePreorder(nod.rt);  
    }  
      
    void traverseInorder(Nod nod)  
    {  
        if (nod == NILL)  
            return;  
        traverseInorder(nod.lft);  
        Console.Write(nod.info + " ");  
        traverseInorder(nod.rt);  
    }  
      
    void traversePostorder(Nod nod)  
    {  
        if (nod == NILL)  
            return;  
        traversePostorder(nod.lft);  
        traversePostorder(nod.rt);  
        Console.Write(nod.info + " ");  
    }  
      
      
    void traversePreorder() { traversePreorder(root); }  
    void traverseInorder() { traverseInorder(root); }  
    void traversePostorder() { traversePostorder(root); }  
      
    static void Main()  
    {  
        BinaryTree bt = new BinaryTree();  
        bt.root = new Nod(37);  
        bt.root.lft = new Nod(27);  
        bt.root.rt = new Nod(47);  
        bt.root.lft.lft = new Nod(22);  
        bt.root.lft.rt = new Nod(32);  
        bt.root.lft.lft.lft = new Nod(12);  
        bt.root.lft.lft.rt = new Nod(25);  
        bt.root.rt.lft = new Nod(42);  
        bt.root.rt.rt = new Nod(57);  
        bt.root.rt.rt.lft = new Nod(52);  
        bt.root.rt.rt.rt = new Nod(67);  
        Console.WriteLine("The Preorder traversal of given binary tree is - ");  
        bt.traversePreorder();  
        Console.WriteLine();  
        Console.WriteLine("The Inorder traversal of given binary tree is - ");  
        bt.traverseInorder();  
        Console.WriteLine();  
        Console.WriteLine("The Postorder traversal of given binary tree is - ");  
        bt.traversePostorder();  
    }  
}  

Output:

Binary search tree traversal in-order pre-order post-order examples

Example 5)

#include <iostream>  
  
using namespace std;  
  
struct nod {  
    int element;  
    struct nod* lft;  
    struct nod* rt;  
};  
  
/*To create a new nod*/  
struct nod* creatNod(int val)  
{  
    struct nod* Nod = (struct nod*)malloc(sizeof(struct nod));  
    Nod->element = val;  
    Nod->lft = NILL;  
    Nod->rt = NILL;  
  
    return (Nod);  
}  
  
/*function to traverse the nods of binary tree in preorder*/  
void traversePreorder(struct nod* root)  
{  
    if (root == NILL)  
        return;  
    cout<<" "<<root->element<<" ";  
    traversePreorder(root->lft);  
    traversePreorder(root->rt);  
}  
  
/*function to traverse the nods of binary tree in Inorder*/  
void traverseInorder(struct nod* root)  
{  
    if (root == NILL)  
        return;  
    traverseInorder(root->lft);  
    cout<<" "<<root->element<<" ";  
    traverseInorder(root->rt);  
}  
  
/*function to traverse the nods of binary tree in postorder*/  
void traversePostorder(struct nod* root)  
{  
    if (root == NILL)  
        return;  
    traversePostorder(root->lft);  
    traversePostorder(root->rt);  
    cout<<" "<<root->element<<" ";  
}  
  
int main()  
{  
    struct nod* root = creatNod(38);  
    root->lft = creatNod(28);  
    root->rt = creatNod(48);  
    root->lft->lft = creatNod(23);  
    root->lft->rt = creatNod(33);  
    root->lft->lft->lft = creatNod(13);  
    root->lft->lft->rt = creatNod(26);  
    root->rt->lft = creatNod(43);  
    root->rt->rt = creatNod(58);  
    root->rt->rt->lft = creatNod(53);  
    root->rt->rt->rt = creatNod(68);  
    cout<<"\n The Preorder traversal of given binary tree is -\n";  
    traversePreorder(root);  
      
    cout<<"\n The Inorder traversal of given binary tree is -\n";  
    traverseInorder(root);  
      
    cout<<"\n The Postorder traversal of given binary tree is -\n";  
    traversePostorder(root);  
    return 0;  
} 

Output:

Binary search tree traversal in-order pre-order post-order examples

Related Topics

Counts the number of times a given element occurs in a Linked List

Counts the number of times a given element occurs in a Linked List This article will explain how we can count the occurrences of a particular element in a list. Here,...

3 minutes read.

Introduction to Arrays

What exactly is an array? A group of related data pieces stored in contiguous memory regions is referred to as an array. It is the most basic data structure in which...

5 minutes read.

Reverse a Linked List in groups of given size

Reverse a Linked List in groups of given size This article will explain how to reverse a linked list in groups of given size. Here we have given a linked list...

2 minutes read.

Complete Binary tree

In this article, we will discuss the complete binary tree. But before start discussing the complete binary tree, we should first see a brief description of a binary tree. What is...

7 minutes read.

Write Main Difference Between Tree and Graph in Data Structures

Graph: The graph has two sets, which are considered V and E. These vertices are also called nodes, and edges are referred to as arcs connecting any two nodes in a...

4 minutes read.

Graph Data Structure

A graph is a non-primitive and non-linear data structure. It is a group of (V, E) where V is a set of vertexes, and E is a set of edge....

3 minutes read.

Cocktail Sort

C Program executes cocktail sort. Combo sort is a somewhat straightforward arranging calculation initially planned by Wlodzimierz Dobosiewicz and Artur Borowy in 1980, later rediscovered by Stephen Lacey and Richard Box...

5 minutes read.

Strings in Data Structures

Strings and functions in C A string is a collection of characters. We'll learn how to declare strings, operate with strings in C programming, and use pre-defined string handling routines. We'll look...

7 minutes read.

Doubly Linked List

Doubly Linked List Doubly linked list is another kind of Linked list. Doubly linked list contains two pointers for navigation. In this, we can traverse the list in both directions, either...

4 minutes read.

Data Structure Prefix to Postfix Conversion

Prefix to Postfix Conversion Prefix: As the name suggests if the operator placed before the operands called the prefix expression.  The form of prefix expression is (operator, operand1, operand2). Example:  *+EF-GH (Infix:...

2 minutes read.

Difference Between Linear and Non Linear Data Structures

Data Structure A data structure is a data object together with the relationships between the instances and the individual elements that compose an instance. These relationships are defined by the operations...

5 minutes read.

What is a full Binary Tree?

A full binary tree is considered to be a special kind of binary tree in which every single node or leaf node present either contains two children or no children...

4 minutes read.

Insertion Sort vs Bubble Sort

In this article, we will see the major differences between Insertion Sort and Bubble Sort. Before that, let’s have a quick overview of what these sorting algorithms are and what’s...

4 minutes read.

LCA of binary tree

Implementation //Writing a program to find the lowest common factor in a given binary search tree. #include <iostream> #include <vector> using namespace std; // the very first step is to create a binary tree. struct __nod { int...

8 minutes read.

What are Forest Trees in Data Structure

Data structure A data model manages and optimizes computer resources, and a database stores and manages data. It's one of many uses for data structures to hold data. Data structures come...

5 minutes read.

Detect Loop in Linked List: Data Structure

Detect the Loop in Linked List: In this problem, we will be seeing some technique through which we can detect the loop in linked list. We will discuss each technique...

3 minutes read.

Given a Binary Tree Return All Root-to-Leaf Paths

Implementation #include <bits/stdc++.h> using namespace std; // A binary tree node generally consists of data, a pointer to the left and right child, and a pointer to the right child.  class __nod { public: int record; __nod* Lft; __nod*...

9 minutes read.

Given a Binary Tree, Check if it's balanced

Implementation /*Creating a C++ program that will help us identify whether the given tree is height-balanced or not.  */ #include <bits/stdc++.h> using namespace std; /* A particular binary tree node consists of data with some...

4 minutes read.

Properties of Binary Tree

Trees are maybe of the most significant datum structures. They are used to store and figure out data. A binarytree is a tree data structure made from nodes, all of which has...

3 minutes read.

Red Black Tree vs AVL Tree: Data Structure

Difference Between Red Black Tree vs AVL Tree Red Black Tree: A red-black tree is referred as self-balancing binary search tree. In red-black, each node stores an extra bit that determines...

4 minutes read.