binary tree

[Reddevil1003]

Found this tutorial code. i cant understand how function inorder() is traversing through binary tree. (i am a beginner, i understand how recursive functions work , but this code has got me confused) L68.

  // C++ program to insert element in Binary Tree
#include <iostream>
#include <queue>
#include<conio.h>
using namespace std;

/* A binary tree node has data, pointer to left child
and a pointer to right child */

struct Node {
	int data;
	Node* left;
	Node* right;
};

/* Function to create a new node */

Node* CreateNode(int data)
{
	Node* newNode = new Node();
	if (!newNode) {
		cout << "Memory error\n";
		return NULL;
	}
	newNode->data = data;
	newNode->left = newNode->right = NULL;
	return newNode;
}

/* Function to insert element in binary tree */

Node* InsertNode(Node* root, int data)
{
	// If the tree is empty, assign new node address to root
	if (root == NULL) {
		root = CreateNode(data);
		return root;
	}

	// Else, do level order traversal until we find an empty
	// place, i.e. either left child or right child of some
	// node is pointing to NULL.
	queue<Node*> q;
	q.push(root);

	while (!q.empty()) {
		Node* temp = q.front();
		q.pop();

		if (temp->left != NULL)
			q.push(temp->left);
		else {
			temp->left = CreateNode(data);
			return root;
		}

		if (temp->right != NULL)
			q.push(temp->right);
		else {
			temp->right = CreateNode(data);
			return root;
		}
	}
}

/* Inorder traversal of a binary tree */

void inorder(Node* temp)
{
	if (temp == NULL)
		return;
    inorder(temp->left);
	cout << temp->data << ' ';
	inorder(temp->right);
}

// Driver code
int main()
{
	Node* root = CreateNode(10);
	root->left = CreateNode(11);
	root->left->left = CreateNode(7);
	root->right = CreateNode(9);
	root->right->left = CreateNode(15);
	root->right->right = CreateNode(8);

	cout << "Inorder traversal before insertion: ";
	inorder(root);
	cout << endl;

	int key = 12;
	root = InsertNode(root, key);

	cout << "Inorder traversal after insertion: ";
	inorder(root);
	cout << endl;

	return 0;
}

[lastchance]

Well, if you are at any node that currently has some assigned data (i.e. isn't NULL) then you would output, in order:

everything smaller than the node's value ...
... then the node's value ...
... then everything larger than the node's value

Grim diagram follows:

                  |
                  |
                 NODE
               /  |  \
              / value \
             /         \
          left        right
           /             \
--------------        ----------------
| Everything |        | Everything   |
| less than  |        | greater than |
| value      |        | value        |
--------------        ----------------

Here's another variant:

#include <iostream>
using namespace std;

class tree
{
   class node
   {
   public:
      int data;
      node *left = nullptr, *right = nullptr;
      node( int v ) : data( v ){}
   };

   node *root = nullptr;

public:
   void insert( int value ){ insert( root, value ); }
   void output()           { output( root );        }

private:
   void insert( node *&ptr, int value );
   void output( node *ptr );
};

void tree::insert( node *&ptr, int value )
{
   if ( !ptr ) ptr = new node( value );
   else if ( value < ptr->data ) insert( ptr->left , value );
   else if ( value > ptr->data ) insert( ptr->right, value );
}

void tree::output( node *ptr )
{
   if ( ptr )
   {
      output( ptr->left );
      cout << ptr->data << ' ';
      output( ptr->right );
   }
}

//=================================================================

int main()
{
   tree T;
   for ( int e : { 10, 11, 7, 9, 15, 8, 12 } ) T.insert( e );
   T.output();
}

7 8 9 10 11 12 15  

          10
          |
   7 -----+---11
   |           |
 --+---9     --+---15
       |            |
     8-+--       12-+---
     |           | 
   --+--       --+--

[seeplus]

i cant understand how function inorder() is traversing through binary tree

The best advice I can provide (and for any linked data structure) is to draw a correctly populated tree on paper with each node showing the left, right and data. Then to follow the code manually - recording variable values etc on paper as the computer would execute the code. Then you can see how it works (or any other linked structure). The same for inserting/removing nodes et al. When I was studying AVL trees for my degree years ago, I found this invaluable to my understanding.

[jonnin]

I mentally convert the recursion to english, or of very confusing stuff, will actually translate it on paper (usually the confusing ones are just someone being snarky and not production code. Weird recursion to show off is a thing online, but rarely done in practice).

so, if you go left as far as you can and then print, what do you get? (7)
then go right one time.
if you go left as far as you can and then print, what do you get? (8)
go right one time (null, return to last unprinted value, 9)
print the 9, go right one time (null, return to last unprinted value, 10)
print 10, go right one time
go left as far as you can... (can't)
print 11 go right one time...
go left as far as you can...
etc

[dutch]

The way to read a recursive function is to NOT FOLLOW THE RECURSIVE CALL. Just assume that the recursive call does what the function is supposed to do. inorder is supposed to print the element values in order. So, reading the code, it says "first print the left side in order, then print the current value, then print the right side in order". That is clearly correct.

I remember this technique being called Method99, the idea being that you imagine a function is called with value/size 100, and the "recursive" calls are all handled with calls to Method99, which properly handles values/sizes of 99 or less. You need to create your function to be able to handle the "size 100" case, using the prewritten Method99 to handle the smaller cases.

So merge sort is something like:

MergeSort:
    if size is less than some small size:
        // sort with insertion sort (or some other simple sort)
        ...
    otherwise:
        // sort first half 
        Method99(first half of data)

        // sort second half 
        Method99(second half of data)

        // merge the halves together
        ...

The "Method99" calls become the recursive calls.

[dhayden]

InsertNode() needs return root; at the end.

A great way to understand recursive code is to add temporary code that prints each time you enter and leave the function:

void inorder(Node* temp)
{
    if (temp == NULL)
        return;
    cout << "Entering inorder(" << temp->data << ")\n";
    inorder(temp->left);
    cout << "\t\t\tPRINT: " << temp->data << '\n';
    inorder(temp->right);
    cout << "Leaving inorder(" << temp->data << ")\n";
}

Inorder traversal before insertion:
Entering inorder(10)
Entering inorder(11)
Entering inorder(7)
                        PRINT: 7
Leaving inorder(7)
                        PRINT: 11
Leaving inorder(11)
                        PRINT: 10
Entering inorder(9)
Entering inorder(15)
                        PRINT: 15
Leaving inorder(15)
                        PRINT: 9
Entering inorder(8)
                        PRINT: 8
Leaving inorder(8)
Leaving inorder(9)
Leaving inorder(10)

Inorder traversal after insertion:
Entering inorder(10)
Entering inorder(11)
Entering inorder(7)
                        PRINT: 7
Leaving inorder(7)
                        PRINT: 11
Entering inorder(12)
                        PRINT: 12
Leaving inorder(12)
Leaving inorder(11)
                        PRINT: 10
Entering inorder(9)
Entering inorder(15)
                        PRINT: 15
Leaving inorder(15)
                        PRINT: 9
Entering inorder(8)
                        PRINT: 8
Leaving inorder(8)
Leaving inorder(9)
Leaving inorder(10)

[lastchance]

Original code:
https://www.geeksforgeeks.org/insertion-in-a-binary-tree-in-level-order/

I guess this tree had no concept of sorting. I should have read it more carefully.

[Reddevil1003]

Thankx @dhayden adding this cleared my concept

oid inorder(Node* temp)
{
    if (temp == NULL)
        return;
    cout<<"\nEntering: "<<temp->data; 
    inorder(temp->left);
    cout<<"\nPrint: "<<temp->data; 
    inorder(temp->right);
    cout<<"\nLeaving: "<<temp->data;
}

@seeplus could you show me any other way for function inorder() other than recursion!!
@lastchance thankx for the help , i am still going through your code.

[seeplus]

For an iterative way to traverse a tree in-order see https://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion/

However IMO using recursion with tree operations where viable is the easiest.

PS The level-order insertion can also be done using recursion rather than iteration using a queue. See https://www.geeksforgeeks.org/construct-a-binary-in-level-order-using-recursion/

[Reddevil1003]

one more thing

struct Node {
	int data;
	Node* left;
	Node* right;
};


Node* CreateNode(int data)
{
        Node* newNode=new Node();
	newNode->data = data;
	newNode->left = newNode->right = nullptr; 
	return newNode;
}
   // or

Node* CreateNode(int data)
{
	Node* newNode{new Node{data}};
	return newNode;
}

both createNode function are same , however in the later code we havent assigned nullptr to the node pointers . How is it so?

and also if we remove this newNode->left = newNode->right = nullptr; it doesnt make any difference.
however removing this line makes defference if we declare new node likeNode* newNode=new Node instead of Node* newNode=new Node();
so adding fuction call operator at the end is the reason but how?

[seeplus]

In the later code it uses the default initialised value for left and right. However, these haven't been default initialised so their value is unknown.

struct Node {
	int data {};
	Node* left {};
	Node* right {};
};

which default initialises the struct member variables. You could do:

Node* CreateNode(int data)
{
    return new Node{data};
}