BST inorder traversing

[Sharan123]

Question :This is a code of inorder traversing in BST , the problem is i can implement code but i am not
100% sure how it works , Now my understanding is when a recursive call is made for temp->left 9 is stored
in stack and than 4,3,1 which is clear to me but when another recursive call is made it has an adrress of
NULL which than output the top most data in stack which is 1 , now the confusing part for me is when
recursive call is made for right pointer of temp , in this example the output should put 6 ,6 and 7
like in this example and print 7 but it doesn't like in left recursive call but it prints 6,6 and 7
which is in right order of increasing data ,please make it clearer how does this right recursive
call work and why does it have different behaviour than left recursive call if any .
Example code:

  #include<iostream>
#include<conio.h>
using namespace std;
struct Tree
{
	int data;
	Tree *left;
	Tree *Right;
};
Tree * root =NULL;

Tree * insert(Tree *temp , int elm)
{
	if(temp==NULL)
	{
		temp = new Tree;
		temp->data=elm;
		temp->left=NULL;
		temp->Right=NULL;
	}
	else 
	{
		if(elm>=temp->data)
			temp->Right=insert(temp->Right,elm);
		else
			temp->left=insert(temp->left,elm);
	}
	return temp;
}
/////////////////////////////////////////////////////////////////////////////////////////
int count=1;
void FirstMin(Tree *temp )
{
	if (count <5)
	{
		temp==NULL;
		//return; this doesn't work too 
	}
	cout<<"Temp : "<<temp<<endl;
	if(temp!=NULL)
	{
		FirstMin(temp->left);
		cout<<"TEMP INNER :"<<temp<<endl;
		cout<<temp->data<<endl;
		count++;
		FirstMin(temp->Right);
	}
}
int main()
{
	root=insert(root,9);
	insert(root,11);
	insert(root,4);
	insert(root,3);
	insert(root,6);
	insert(root,22);
	insert(root,1);
	insert(root,6);
        insert(root,21);
	insert(root,7);
        FirstMin(root);
	getch();
}

[JockX]

Please, run this modified code. I made it print out more output. It is indented, to better reflect at which level of recursion are at any given time. Notice the order in which "Now in ... " and "Out of ..." lines are printed to better understand what is going on.
Also, notice, this will ignore count loop entirely, and function will go only once + recursive calls:

// in main add 0 to FirstMin call (line 61):
FirstMin(root, 0);

void FirstMin(Tree *temp, int level)
{
  // This section will make things easier to see when printed 
  char indent[100];
  for (int i = 0; i < level; i++){
    indent[i] = '\t';
  }
  indent[level] = 0;

  cout << indent << "# Now in : " << temp << " data: ";
  if (temp != NULL)
  {
    cout << temp->data << endl;
    cout << indent << "< Going left to: " << temp->left << endl;
    FirstMin(temp->left, level + 1);
    counter++;

    cout << indent << "> Going right to: " << temp->Right << endl;
    FirstMin(temp->Right, level + 1);
  }
  else cout << "NULL" << endl;
  cout << indent << "^ Out of " << temp << endl;
}

Compare it with actual data layout inside a tree:

     root: 9
        /     \
      4        11
    /  \      /  \
  3       6  NULL  22
 / \     / \      /  \
1 NULL  6   7    21  NULL

[Sharan123]

Thank you but still there are problems i have seen your code it clears up somethings but i am still confused in some parts of traversing , though it will be hard to convey herez a sample code for my problem

int main()
{
	root=insert(root,9);
	insert(root,11);
	insert(root,4);
	insert(root,3);
	insert(root,6);
	insert(root,22);
	insert(root,1);
	insert(root,6);
        insert(root,21);
		insert(root,5);
	insert(root,7);
	insert(root,0);
	insert(root,5);
	insert(root,2);
	string name="ROOT";
        Experiment(root,name);
	getch();
void Experiment (Tree * temp ,string x)
{
	if(temp !=NULL)
	{
		cout<<"1 :"<<x<<":"<<temp->data<<endl;
		Experiment (temp ->left,"left");
		cout<<"2 :"<<x<<":"<<temp->data<<endl;
		Experiment(temp->Right,"RIGHT");
		cout<<"3 :"<<x<<":"<<temp->data<<endl;
		
	}
}
}

In this code why is 4 printed 1 time ? //it should be printed 2 times like 3
In this code why is 5 printed(where 5 is in recurring sequence not total) printed 6 times // it should be printed five times

[JockX]

If you look at it in the flat way - each number is printed three times: at 1:, 2: and 3: .
This is actually what is happening. Just notice, each time Experiment is called recursively, a new instance of this function starts from the begining, so it's output cuts in. Once there are no more recursive calls, the higher level function continues from where it was interupted.

You are inserting 5 into the tree twice. so it is printed three times for each, that is six. With indentation it makes more sense:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

1 :ROOT:9 1 :left:4 // first four 1 :left:3 1 :left:1 1 :left:0 2 :left:0 3 :left:0 2 :left:1 1 :RIGHT:2 2 :RIGHT:2 3 :RIGHT:2 3 :left:1 2 :left:3 3 :left:3 2 :left:4 // second four 1 :RIGHT:6 1 :left:5 2 :left:5 1 :RIGHT:5 2 :RIGHT:5 3 :RIGHT:5 3 :left:5 2 :RIGHT:6 1 :RIGHT:6 2 :RIGHT:6 1 :RIGHT:7 2 :RIGHT:7 3 :RIGHT:7 3 :RIGHT:6 3 :RIGHT:6 3 :left:4 // third four 2 :ROOT:9 1 :RIGHT:11 2 :RIGHT:11 1 :RIGHT:22 1 :left:21 2 :left:21 3 :left:21 2 :RIGHT:22 3 :RIGHT:22 3 :RIGHT:11 3 :ROOT:9

1 :ROOT:9 | 1 :left:4 | | 1 :left:3 | | | 1 :left:1 | | | | 1 :left:0 | | | | 2 :left:0 | | | | 3 :left:0 | | | 2 :left:1 | | | | 1 :RIGHT:2 | | | | 2 :RIGHT:2 | | | | 3 :RIGHT:2 | | | 3 :left:1 | | 2 :left:3 | | 3 :left:3 | 2 :left:4 | | 1 :RIGHT:6 | | | 1 :left:5 | | | 2 :left:5 | | | | 1 :RIGHT:5 | | | | 2 :RIGHT:5 | | | | 3 :RIGHT:5 | | | 3 :left:5 | | 2 :RIGHT:6 | | | 1 :RIGHT:6 | | | 2 :RIGHT:6 | | | | 1 :RIGHT:7 | | | | 2 :RIGHT:7 | | | | 3 :RIGHT:7 | | | 3 :RIGHT:6 | | 3 :RIGHT:6 | 3 :left:4 2 :ROOT:9 | 1 :RIGHT:11 | 2 :RIGHT:11 | | 1 :RIGHT:22 | | | 1 :left:21 | | | 2 :left:21 | | | 3 :left:21 | | 2 :RIGHT:22 | | 3 :RIGHT:22 | 3 :RIGHT:11 3 :ROOT:9