Insertion in binary search tree without recursion in c++
C++ program for Insertion in binary search tree without recursion. Here problem description and explanation.
// Include header file
#include <iostream>
using namespace std;
// C++ program for
// iterative insert in binary search tree
class TreeNode
{
public:
int data;
TreeNode *left;
TreeNode *right;
TreeNode(int data)
{
this->data = data;
this->left = nullptr;
this->right = nullptr;
}
};
class BinarySearchTree
{
public: TreeNode *root;
BinarySearchTree()
{
this->root = nullptr;
}
//insert a element
void addNode(int data)
{
// Create a new node
TreeNode *node = new TreeNode(data);
if (this->root == nullptr)
{
// When adds a first node in bst
this->root = node;
}
else
{
TreeNode *find = this->root;
// Add new node to proper position
while (find != nullptr)
{
if (find->data >= data)
{
if (find->left == nullptr)
{
// When left child empty
// So add new node here
find->left = node;
return;
}
else
{
// Otherwise
// Visit left sub-tree
find = find->left;
}
}
else
{
if (find->right == nullptr)
{
// When right child empty
// So add new node here
find->right = node;
return;
}
else
{
// Visit right sub-tree
find = find->right;
}
}
}
}
}
// Display preorder
void preorder(TreeNode *node)
{
if (node != nullptr)
{
// Display node value
cout << " " << node->data;
// Visit to left subtree
this->preorder(node->left);
// Visit to right subtree
this->preorder(node->right);
}
}
void inorder(TreeNode *node)
{
if (node != nullptr)
{
// Visit to left subtree
this->inorder(node->left);
// Display node value
cout << " " << node->data;
// Visit to right subtree
this->inorder(node->right);
}
}
void postorder(TreeNode *node)
{
if (node != nullptr)
{
// Visit to left subtree
this->postorder(node->left);
// Visit to right subtree
this->postorder(node->right);
// Display node value
cout << " " << node->data;
}
}
};
int main()
{
BinarySearchTree *tree = new BinarySearchTree();
/*
10
/ \
/ \
4 15
/ \ /
3 5 12
-------------
Build binary search tree
*/
tree->addNode(10);
tree->addNode(4);
tree->addNode(3);
tree->addNode(5);
tree->addNode(15);
tree->addNode(12);
// Display tree nodes
cout << "Preorder " << endl;
tree->preorder(tree->root);
cout << "\nInorder " << endl;
tree->inorder(tree->root);
cout << "\nPostorder " << endl;
tree->postorder(tree->root);
return 0;
}
Output
Preorder
10 4 3 5 15 12
Inorder
3 4 5 10 12 15
Postorder
3 5 4 12 15 10
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment