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

Linked List Data Structure

Linked list in DS: The linked list is a non-primitive and linear data structure. It is a list of a particular type of data element that is connected to each...

3 minutes read.

Given a Binary Tree Swap Nodes at K Height

Implementation // Writing a C++ program that will help us exchange the nodes.  #include<bits/stdc++.h> using namespace std; // Creating a binary tree node. struct __nod { int record; struct __nod *Lft, *Rt; }; // creating a function that will help...

8 minutes read.

Binary Tree Uses

A binary tree is a tree data structure containing hubs with at most two children for instance a right and left child. The node at the top is insinuated as the...

3 minutes read.

Heap Sort in Data Structure

Heap Sort A heap is a tree-based data structure that has specific properties. Heap is always a complete binary tree (CBT). That is, all the nodes of the tree are completely filled.If...

6 minutes read.

Blowfish algorithm

The Blowfish algorithm is the very first encryption algorithm which is symmetric. It was firstly used as an alternate algorithm for the DES algorithm. It was designed by Bruce Steiner...

3 minutes read.

Convert Sorted List to Binary Search Tree

Implementation // creating the C++ implementation of the following approach: - #include <bits/stdc++.h> using namespace std; /* Create the link list node and see its implementation. */ class L__Nod { public: int record; L__Nod* next; }; /* constructing a new binary...

15 minutes read.

Binary Tree vs Binary Search Tree: Data Structure

Difference Between Binary Tree and Binary Search Tree What is Binary Tree? A tree which each node can have utmost two children called binary tree. These children are referred as the ‘left...

3 minutes read.

Binary Search

Binary Search: When there is a large data structure, the linear search takes a lot of time to search the element. The binary search was developed to overcome the lack...

7 minutes read.

Winner tree in Data Structures

Tree Data structure A tree is a hierarchical and non-linear data structure with nodes. Each node in the Tree contains a message value and stores the name passed to another ("child")...

6 minutes read.

Counting Sort

Counting Sort: Counting sort is a sorting algorithm that is used to sort the elements of the array within a specific range. It counts the same element number of the...

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

Preorder Traversal of Binary Trees

In general, Stack, Array, Queue, and other linear data structures only have one way to traverse the data. However, there are numerous ways to traverse through the data in a hierarchical...

3 minutes read.

Extended Binary Tree

An extended binary tree is a binary tree in which all the NILL subtrees present mainly in the original trees are exchanged with the special nodes that are primarily known...

3 minutes read.

Advantages and Disadvantages of Linked List

Advantages of Linked List The linked list is a dynamic data structure.You can also decrease and increase the linked list at run-time. That is, you can allocate and deallocate memory at...

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

Burning binary tree

Burn the Binary tree starting from the target node You have given a binary tree and a target node value. Now you have to burn the tree from target node. You...

4 minutes read.

Equal Sum

Find an element in array such that the sum of left array is equal to the sum of right array You have been given an array of numbers. You have to...

4 minutes read.

Threaded Binary Trees

Introduction Threaded Binary Trees (TBTs) are an enhancement of normal binary trees intended for in-order traversal only. This means that this data structure is developed with the objective of making the...

12 minutes read.

Tree in Data Structure

Tree A tree is a non-linear data structure by which hierarchical data is displayed. As we know that there are many trees in the forest, similarly the data structure also contains...

3 minutes read.

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

4 minutes read.