Binary Search Tree In C++ Using Non-recursive Methods

By Ashwini Laxman Jadhav

In this tutorial, You learn how to implement an insertion(), level-wise printing(), and traversals in a binary search tree using non-recursive methods.

A binary Search Tree can be implemented using recursion also but using recursion the time complexity of your program is maximum. so to avoid this in this tutorial, we will learn how to implement a binary search tree using non-recursive methods.

Non-recursive Implementation Of Binary Search Tree In C++

In this tutorial, we will discuss stack and queue because in the traversal of the tree and in level-wise printing of the tree we use stack and queue concepts. In a binary search tree, we have three traversal methods 

1] In-order Traversal

2] Pre-order Traversal

3] Post-order Traversal

- In in-order traversal, we need to travel from the first left node then the root, and at the last right node.

order:- LEFT --> ROOT --> RIGHT.

- In pre-order traversal, we need to travel from the first root node then the left node, and at the last right node.

order:-   ROOT -->LEFT --> RIGHT.

- In post-order traversal, we need to travel from the first right node then the left, and the last root node.

order:- LEFT --> ROOT --> RIGHT.

So, for implementing these traversals we need to use stack and queue methods and in level-wise printing, you will print the first root then the left, and then the right node of your tree. and in insertion, you need to compare your root data with the new data which you are entering. if root data is greater than your new data then insert it to the right subtree and if root data is smaller than new data then insert it to the left subtree.

Some portion of your source code is here if you want the whole source code then download it from the below file section.

#include<bits/stdc++.h>
using namespace std;

class node
{
  public:
    int data;
    node* left;
    node* right;
    
    node(int val)
    {
      data=val;
      left=NULL;
      right=NULL;
    }