Tree data structure tutorial 6. Implementation of Binary tree in C++

Implement below operations on Binary Tree

#include<iostream>
#include<vector>
#include<string>
#include<queue>

using namespace std;


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

    Node(int x)
    {
    	data = x;
    	left = NULL;
    	right = NULL;
    }
};

//global root declaration
Node *root;

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

void preOrder(Node *root)
{
        if (!root)
                return;
        cout << root->data << " ";
        preOrder(root->left);
        preOrder(root->right);
}
void postOrder(Node *root)
{
        if (!root)
                return;
        postOrder(root->left);
        postOrder(root->right);
        cout << root->data << " ";
}

int getHeight(Node *root)
{
        if (!root)
                return 0;
        return 1 + max(getHeight(root->left) , getHeight(root->right));
}

bool iterativeSearch(Node *root, int key) 
{ 
    // Base Case 
    if (root == NULL) 
        return false; 
  
    // Create an empty queue for level order traversal 
    queue<Node *> q; 
  
    // Enqueue Root and initialize height 
    q.push(root); 
  
    // Queue based level order traversal 
    while (q.empty() == false) 
    { 
        // See if current node is same as key 
        Node *node = q.front(); 
        if (node->data == key) 
            return true; 
  
        // Remove current node and enqueue its children 
        q.pop(); 

        if (node->left != NULL) 
            q.push(node->left); 

        if (node->right != NULL) 
            q.push(node->right); 
    } 
  
    return false; 
} 


int findMax(Node* root) 
{ 
    // Base case 
    if (root == NULL) 
      return INT_MIN; 
  

    int result = root->data; 

   	// Find the maximum value in left sub-tree
    int lres = findMax(root->left); 

  	// Find the maximum value in right sub-tree
    int rres = findMax(root->right); 

    if (lres > result) 
      result = lres; 
    if (rres > result) 
      result = rres; 

    return result; 
}


int findMin(Node* root) 
{ 
    // Base case 
    if (root == NULL) 
      return INT_MAX; 
  

    int result = root->data; 

   	// Find the maximum value in left sub-tree
    int lres = findMin(root->left); 

  	// Find the maximum value in right sub-tree
    int rres = findMin(root->right); 

    if (lres < result) 
      result = lres; 
    if (rres < result) 
      result = rres; 
  
    return result; 
}  

bool isBalanced(Node *root)
{
        if (!root)
                return false;
        int leftHeight = getHeight(root->left);
        int rightHeight = getHeight(root->right);

        if (abs(leftHeight - rightHeight) > 1)
                return false;
        return true;
}

void deleteTree(Node* node)  
{ 
    if (node == NULL) return; 
  
    /* first delete both subtrees */
    deleteTree(node->left); 
    deleteTree(node->right); 
    
    /* then delete the node */
    cout<<"\n Deleting node = "<<node->data<<endl; 
    free(node); 
}  
  
int main()
{	
	root = new Node(1);

  	/* 
 
        1    
  */


	root -> left = new Node(2);
	root -> right = new Node(3);
	
	/*  
  
        1 
      /   \ 
     2     3   
  */
	root -> left -> left = new Node(4);

	/*
  
        1 
      /   \ 
     2     3
    /
   4   
  */

	root -> left -> right = new Node(8);
	root -> left -> right -> right = new Node(5);
	root -> left -> right -> left = new Node(6);


	root -> left -> left -> right = new Node(15);
	root -> left -> left -> left = new Node(16);



	cout<<"\nThe values displayed using inorder traversal = "<<endl;
	inorder(root); 

	cout<<"\nThe values displayed using preOrder traversal = "<<endl;
	preOrder(root); 

	cout<<"\nThe values displayed using postOrder traversal = "<<endl;
	postOrder(root); 

	int maxValue = findMax(root);
	cout<<"\n\nThe maximum value is "<< maxValue <<endl;

	int minValue = findMin(root);
	cout<<"\nThe minumim value is "<< minValue <<endl;

	cout<<"\nThe height of the tree is = "<< getHeight(root)<<endl;

	if(isBalanced(root))
		cout<<"\nThe tree is balanced"<<endl;
	else
		cout<<"\nThe tree not is balanced"<<endl;


	int key = 16;
	if(iterativeSearch(root, key))
		cout<<"\nThe key "<<key<<" is present\n"<<endl;
	else
		cout<<"\nThe key "<<key<<" is not present\n"<<endl;

	cout<<"Deleting entire tree"<<endl;
	deleteTree(root);

}

The values displayed using inorder traversal =
16 4 15 2 6 8 5 1 3
 
The values displayed using preOrder traversal =
1 2 4 16 15 8 6 5 3
 
The values displayed using postOrder traversal =
16 15 4 6 5 8 2 3 1
 
The maximum value is 16
 
The minimum value is 1
 
The height of the tree is = 4
 
The tree not is balanced
 
The key 16 is present
 
Deleting entire tree
 
 Deleting node = 16
 
 Deleting node = 15
 
 Deleting node = 4
 
 Deleting node = 6
 
 Deleting node = 5
 
 Deleting node = 8
 
 Deleting node = 2
 
 Deleting node = 3
 
 Deleting node = 1