My question is with traversing. In my problem the sequence of the traversal is not following as it should. I am using the general logic for the inorder, preorderand the postorder traversal but it is giving in the wrong sequence.
My problem is my code is not traversing like my expected output. The expected output should look like this:
Initially, how many integers you want:
5
Enter the integers: 7 9 1 2 10
Press 1 for inorder traverse, 2 for preorder traverse, 3 for postorder traverse, 4 for inserting new item, 5
for deleting an item, or 6 for exit the program:
4
Enter the item for insert:
2
This item already exists.
Press 1 for inorder traverse, 2 for preorder traverse, 3 for postorder traverse, 4 for inserting new item, 5
for deleting an item, or 6 for exit the program:
4
Enter the item for insert:
8
This item is inserted.
Press 1 for inorder traverse, 2 for preorder traverse, 3 for postorder traverse, 4 for inserting new item, 5
for deleting an item, or 6 for exit the program:
5
Enter the item for delete:
12
This item not found.
Press 1 for inorder traverse, 2 for preorder traverse, 3 for postorder traverse, 4 for inserting new item, 5
for deleting an item, or 6 for exit the program:
5
Enter the item for delete:
7
This item is deleted.
Press 1 for inorder traverse, 2 for preorder traverse, 3 for postorder traverse, 4 for inserting new item, 5
for deleting an item, or 6 for exit the program:
1
**Inorder Traverse: 1 2 8 9 10**
Press 1 for inorder traverse, 2 for preorder traverse, 3 for postorder traverse, 4 for inserting new item, 5
for deleting an item, or 6 for exit the program:
2
**Preorder Traverse: 2 1 9 8 10**
Press 1 for inorder traverse, 2 for preorder traverse, 3 for postorder traverse, 4 for inserting new item, 5
for deleting an item, or 6 for exit the program:
3
**Postorder Traverse: 1 8 10 9 2**
Press 1 for inorder traverse, 2 for preorder traverse, 3 for postorder traverse, 4 for inserting new item, 5
for deleting an item, or 6 for exit the program:
6
Program terminated
But my output is showing the traversal like this:
Inorder Traverse: 1 2 8 9 10
Preorder Traverse: 8 1 2 9 10
Postorder Traverse: 2 1 10 9 8
My code is given below:
#include <iostream>
using namespace std;
struct Node
{
int data;
Node *left;
Node *right;
Node(int value) : data(value), left(nullptr), right(nullptr) {}
};
class BST
{
private:
Node *root;
Node *insertRecursive(Node *root, int value)
{
if (root == nullptr)
{
return new Node(value);
}
if (value < root->data)
{
root->left = insertRecursive(root->left, value);
}
else if (value > root->data)
{
root->right = insertRecursive(root->right, value);
}
else
{
cout << "This item already exists." << endl;
}
return root;
}
Node *findMin(Node *root)
{
while (root->left != nullptr)
{
root = root->left;
}
return root;
}
Node *deleteRecursive(Node *root, int value)
{
if (root == nullptr)
{
cout << "Item not found." << endl;
return nullptr;
}
if (value < root->data)
{
root->left = deleteRecursive(root->left, value);
}
else if (value > root->data)
{
root->right = deleteRecursive(root->right, value);
}
else
{
if (root->left == nullptr)
{
Node *temp = root->right;
delete root;
return temp;
}
else if (root->right == nullptr)
{
Node *temp = root->left;
delete root;
return temp;
}
Node *temp = findMin(root->right);
root->data = temp->data;
root->right = deleteRecursive(root->right, temp->data);
}
return root;
}
void inorderTraversal(Node *root)
{
if (root == nullptr)
{
return;
}
inorderTraversal(root->left);
cout << root->data << " ";
inorderTraversal(root->right);
}
void preorderTraversal(Node *root)
{
if (root == nullptr)
{
return;
}
cout << root->data << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}
void postorderTraversal(Node *root)
{
if (root == nullptr)
{
return;
}
postorderTraversal(root->left);
postorderTraversal(root->right);
cout << root->data << " ";
}
bool searchRecursive(Node *root, int value)
{
if (root == nullptr)
{
return false;
}
if (value < root->data)
{
return searchRecursive(root->left, value);
}
else if (value > root->data)
{
return searchRecursive(root->right, value);
}
else
{
return true;
}
}
public:
BST() : root(nullptr) {}
void insert(int value)
{
root = insertRecursive(root, value);
}
void remove(int value)
{
root = deleteRecursive(root, value);
}
bool search(int value)
{
return searchRecursive(root, value);
}
void inorder()
{
cout << "Inorder Traverse: ";
inorderTraversal(root);
cout << endl;
}
void preorder()
{
cout << "Preorder Traverse: ";
preorderTraversal(root);
cout << endl;
}
void postorder()
{
cout << "Postorder Traverse: ";
postorderTraversal(root);
cout << endl;
}
};
int main()
{
BST bst;
int n, choice, item;
cout << "Initially, how many integers do you want: ";
cin >> n;
cout << "Enter the integers: ";
for (int i = 0; i < n; i++)
{
cin >> item;
bst.insert(item);
}
cout << endl;
while (true)
{
cout << "Press 1 for inorder traverse, 2 for preorder traverse, "
<< "3 for postorder traverse, 4 for inserting new item, "
<< "5 for deleting an item, or 6 for exit the program: " << endl;
cin >> choice;
switch (choice)
{
case 1:
bst.inorder();
cout << endl;
break;
case 2:
bst.preorder();
cout << endl;
break;
case 3:
bst.postorder();
cout << endl;
break;
case 4:
cout << "Enter the item for insert: " << endl;
cin >> item;
bst.insert(item);
cout << endl;
break;
case 5:
cout << "Enter the item for delete: ";
cin >> item;
bst.remove(item);
cout << endl;
break;
case 6:
cout << "Program terminated." << endl;
return 0;
default:
cout << "Invalid choice. Please try again." << endl;
}
}
return 0;
}
Your code is correct, but it applies a different approach for deleting a node from the tree. There are several correct ways to delete a node, and they lead to different trees. The "expected output" will find the predecessor node when the node to delete has two children. Your code finds the successor node in that scenario. Both approaches are fine.
If you want to align your code with the "expected output", then change this:
Node *temp = findMin(root->right);
root->data = temp->data;
root->right = deleteRecursive(root->right, temp->data);
to this:
Node *temp = findMax(root->left);
root->data = temp->data;
root->left = deleteRecursive(root->left, temp->data);
And define findMax as follows:
Node *findMax(Node *root)
{
while (root->right != nullptr)
{
root = root->right;
}
return root;
}