I'm trying to add elements enter by the user in a BST.For this I've used 2 functions, one is used to create the function and other is just used to insert element to the tree. One is a pre-order function that is used to check if insertion is done or not Initially I tried to add elements manually.Its not printing all inserted values.
The overall layout
struct Node{
int data;
struct Node* left;
struct Node* right;
};
void Inorder(struct Node* root){
if(root==NULL){
return;
}
else{
Inorder(root->left);
cout<<root->data<<" ";
Inorder(root->right);
}
}
struct Node* create_node(int data){
struct Node* node=(struct Node*) malloc(sizeof(struct Node));
node->data=data;
node->left=NULL;
node->right=NULL;
return node;
}
The problem code:-
struct Node* insert(struct Node* root,int data){
static struct Node* prev=NULL;
if(root==NULL && prev==NULL){
return create_node(data);
}
if(root->data==data){
return root;
}
else{
if(root==NULL){
struct Node* ptr=create_node(data);
if(prev->data>data){
prev->left=ptr;
return root;
}
else{
prev->right=ptr;
return root;
}
}
else{
if(root->data>data){
prev=root;
insert(root->left,data);
}
else{
prev=root;
insert(root->right,data);
}
}
}
}
MAIN
int main()
{
struct Node* root=NULL;
root=insert(root,5);
Inorder(root);
cout<<endl;
insert(root,3);
Inorder(root);
insert(root,10);
Inorder(root);
return 0;
}
One thing I noticed that prev is static once we call insert for inserting next element(here 3) it won't roll over from start again because it is declared static.To overcome that Tried to optimize the problem code by making prev as global and making null in main every time I call insert function in the main(), The optimised code is as follows:
#include <iostream>
#include<stdlib.h>
using namespace std;
static struct Node* prev=NULL;
struct Node{
int data;
struct Node* left;
struct Node* right;
};
void Inorder(struct Node* root){
if(root==NULL){
return;
}
else{
Inorder(root->left);
cout<<root->data<<" ";
Inorder(root->right);
}
}
struct Node* create_node(int data){
struct Node* node=(struct Node*) malloc(sizeof(struct Node));
node->data=data;
node->left=NULL;
node->right=NULL;
return node;
}
struct Node* insert(struct Node* root,int data){
if(root==NULL && ::prev==NULL){
return create_node(data);
}
if(root->data==data){
return root;
}
else{
if(root==NULL){
struct Node* ptr=create_node(data);
if(::prev->data>data){
::prev->left=ptr;
return root;
}
else{
::prev->right=ptr;
return root;
}
}
else{
if(root->data>data){
::prev=root;
insert(root->left,data);
}
else{
::prev=root;
insert(root->right,data);
}
}
}
}
int main()
{
struct Node* root=NULL;
root=insert(root,5);
Inorder(root);
cout<<endl;
::prev=NULL;
insert(root,3);
Inorder(root);
::prev=NULL;
insert(root,10);
Inorder(root);
return 0;
}
The issue that I noticed in my code (Unfortunately unable to upload the snippet). was in the part mentioned below.
if(root->data==data){
return root;
}
Firstly let me explain the recursion function, at beginning the root would be null at insertion(here inserting 5 as root) so first condition will be satisfied i.e.
if(root==NULL && ::prev==NULL){
return create_node(data);
}
and the function would return,now I set the global variable prev as NULL because I want to traverse again from the root of the tree to add the next element.
Now once we try to add another element (here adding element 3). This condition
if(root==NULL && ::prev==NULL){
return create_node(data);
}
won't be true, now the thought process while writing the logic was checking if at some stage while traversing down the tree if we encounter node with same value then we'll return the root and terminate the function. This is what I tried to implement . Here's the code if you could relate(Problem Code Snippet)
else if(root->data==data){
return root;
}
No doubt approach is fine but I forgot to add one condition(actually I preempted that at this stage the root won't be NULL) but root can be NULL.
Because of this we will face segmentation fault error (in debugger mode -> which helped me to find the error in my code!).
So the correct code would be:
else if(root && root->data==data){// or if(root!=NULL && root->data=data)
return root;
}
Rest of the code remains unaltered
So to sum up when traversing through tree we return true for all conditions and once we reach NULL then since first condition won't we satisfied as prev!=NULL, so it comes to next condition root->data==data but here root=NULL so we get
segmentation fault error and function never encounters ROOT==NULL which was designed for this purpose only i.e. to add/insert element in the tree as everything seems fine on traversing the tree. So to over come this problem I modified my else if condition i.e. else if(root && root->data==data)
struct Node* insert(struct Node* root,int data){
if(root==NULL && ::prev==NULL){
return create_node(data);
}
else if(root && root->data==data){
return root;
}
else{
if(root==NULL){
struct Node* ptr=create_node(data);
if(::prev->data>data){
::prev->left=ptr;
return root;
}
else{
::prev->right=ptr;
return root;
}
}
else{
if(root->data>data){
::prev=root;
insert(root->left,data);
}
else{
::prev=root;
insert(root->right,data);
}
}
}
}
PS: The code was executed for many trees including one mentioned in the question and got the expected results i.e. Inorder was a sorted array which depicts that insertion was done correctly.