Btree.cpp

#include <iostream>
#include <stack>
#include <queue>
#include <climits>
using namespace std;

class BTNode
{
	public:
	int data;
	BTNode *left;
	BTNode *right;
	
		BTNode(){
			data=0;
			left=right=NULL;
		}
};

class BinaryTree{
	
	
	public:
		
	BTNode* newNode(int key);
	void inorder(BTNode *root);
	void inorderIterative(BTNode *root);
	void postorder(BTNode *root);
	void postorderIterative(BTNode *root);
	void preorder(BTNode *root);
	void preorderIterative(BTNode *root);

	void LevelOrder(BTNode *root);
	int findMax(BTNode *root);
	int findMaxLevelOrder(BTNode *root);

	int findElement(BTNode *root,int key);
	BTNode* findElementLevelOrder(BTNode *root,int key);
	
	void insertLevelOrder(BTNode *root,int key);

	int sizeOfBinaryTree(BTNode *root);
	int sizeOfBinaryTreeLevelOrder(BTNode *root);

	void reverseLevelOrder(BTNode *root);
	void deleteBinaryTree(BTNode *root);

	int height(BTNode *root);
	int heightLevelOrder(BTNode *root);
	BTNode* findDeepestNode(BTNode *root);
	int deleteNode(BTNode *root,int key);//has some issues need to resolve

	BTNode* findAncestor(BTNode *root,int key);

	int NumberOfLeavesLevelOrder(BTNode *root);
	int NumberOfFullNodesLevelOrder(BTNode *root);
	int NumberOfHalfNodesLevelOrder(BTNode *root);
	int AreStructurallyIdentical(BTNode *root1,BTNode *root2);

	int DiameterOfTree(BTNode *root);
	BTNode * findLCA(BTNode *root,int n1,int n2);

};

BTNode * BinaryTree::findLCA(BTNode *root,int n1,int n2){
	if(root==0)
		return NULL;
	if(root->data==n1||root->data==n2)
		return root;

	BTNode *leftLCA = findLCA(root->left,n1,n2);
	BTNode *rightLCA = findLCA(root->right,n1,n2);

	if(leftLCA&&rightLCA) return root;

	return (leftLCA!=NULL)?leftLCA:rightLCA;
}

int BinaryTree::DiameterOfTree(BTNode *root){
	if(root==0)return 0;

	int lheight=height(root->left);
	int rheight=height(root->right);

	int lDiameter=DiameterOfTree(root->left);
	int rDiameter=DiameterOfTree(root->right);

	return max(lheight +rheight +1,max(lDiameter,rDiameter));
}
int BinaryTree::AreStructurallyIdentical(BTNode *root1,BTNode *root2){
	if(root1==NULL&&root2==NULL)
		return 1;
	if(root1==NULL||root2==NULL)
		return 0;
	return (root1->data==root2->data&&AreStructurallyIdentical(root1->left,root2->left)&&AreStructurallyIdentical(root1->right,root2->right));
}
int BinaryTree::NumberOfHalfNodesLevelOrder(BTNode *root){
	queue<BTNode*> q;
	q.push(root);
	int count=0;
	while(!q.empty()){
		root=q.front();q.pop();
		if(!root->left&&root->right||root->left&&!root->right)
			count++;
		
		if(root->left)
			q.push(root->left);
		if(root->right)
			q.push(root->right);

		
	}
	return count;
}
int BinaryTree::NumberOfFullNodesLevelOrder(BTNode *root){
	queue<BTNode*> q;
	q.push(root);
	int count=0;
	while(!q.empty()){
		root=q.front();q.pop();
		if(root->left&&root->right)
			count++;
		
		if(root->left)
			q.push(root->left);
		if(root->right)
			q.push(root->right);

		
	}
	return count;
}
int BinaryTree::NumberOfLeavesLevelOrder(BTNode *root){
	queue<BTNode*> q;
	q.push(root);
	int count=0;
	while(!q.empty()){
		root=q.front();q.pop();
		if(!root->left&&!root->right)
			count++;
		else {
			if(root->left)
			q.push(root->left);
		if(root->right)
			q.push(root->right);

		}
	}
	return count;
}
int BinaryTree::deleteNode(BTNode *root,int key){

	/*
	1. find element
	2. find deepest node
	3. swap them
	4. delete deeepest
	*/

	BTNode *el = findElementLevelOrder(root,key);
	if(!el)
		return -1;
	BTNode *deep = findDeepestNode(root);
	
	int tmp = el->data;
	el->data=deep->data;
	
	deep->data=-1;
	BTNode *p=findAncestor(root,-1);
	cout<<' '<<p->data;
	//p->left=p->right=NULL;

	

	//delete deep;

	//delete deep;
	return 1;



}
BTNode* BinaryTree::findAncestor(BTNode *root, int target)
{
  /* base cases */
  if (root == NULL)
     return NULL;
 
  if (root->data == target)
     return root;
 
  /* If target is present in either left or right subtree of this node,
     then print this node */
  if ( findAncestor(root->left, target) ||
       findAncestor(root->right, target) )
  
    //cout << root->data << " ";
    return root;
  
 
  /* Else return false */
  return NULL;
}
BTNode* BinaryTree::findDeepestNode(BTNode *root){
	queue<BTNode*> q;
	q.push(root);
	
	while(!q.empty()){
		root=q.front();q.pop();
		if(root->left)
			q.push(root->left);
		if(root->right)
			q.push(root->right);

	}
	return root;
}
int BinaryTree::heightLevelOrder(BTNode *root){
	int level=0;
	queue<BTNode*> q;
	q.push(root);
	q.push(NULL);
	while(!q.empty()){
		root=q.front();q.pop();
		if(root==NULL){
			if(!q.empty())
				q.push(NULL);
			level++;
		}
		else{
			if(root->left)
			q.push(root->left);
		if(root->right)
			q.push(root->right);

		}
	}
	return level;
}
int BinaryTree::height(BTNode *root){
	
	if(root==NULL)
		return 0;
	return (1+max(height(root->left),height(root->right)));
}
void BinaryTree::deleteBinaryTree(BTNode *root){
	if(root==0)
		return;
	deleteBinaryTree(root->left);
	deleteBinaryTree(root->right);

	delete root;
}
void BinaryTree::reverseLevelOrder(BTNode *root){
	if(!root)return;
	queue<BTNode *> q;
	stack<int> s;
	q.push(root);
	while(!q.empty()){
		root=q.front();q.pop();	
		if(root->right)
			q.push(root->right);
		if(root->left)
			q.push(root->left);
		s.push(root->data);
	}
	while(!s.empty()){
		cout<<s.top()<<' ';
		s.pop();
	}
}
int BinaryTree::sizeOfBinaryTreeLevelOrder(BTNode *root){
	int size=0;
	queue<BTNode*> q;
	q.push(root);
	while(!q.empty()){
		root=q.front();q.pop();
			size++;
		if(root->left)
			q.push(root->left);
		if(root->right)
			q.push(root->right);

	}
	return size;
}
int BinaryTree::sizeOfBinaryTree(BTNode *root){
	if(root)
		return (sizeOfBinaryTree(root->left)+1+sizeOfBinaryTree(root->right));
	else return 0;
}
void BinaryTree::insertLevelOrder(BTNode *root,int key){
	BTNode *tmp=new BTNode;
	tmp->data=key;
	tmp->left=tmp->right=0;

	queue<BTNode*> q;
	q.push(root);
	while(!q.empty()){
		root=q.front();q.pop();
		if(root->left)
			q.push(root->left);
		else
			{root->left=tmp;return;}
		if(root->right)
			q.push(root->right);
		else {root->right=tmp;return;}
	}

}
BTNode* BinaryTree::findElementLevelOrder(BTNode *root,int key){
	queue<BTNode*> q;
	q.push(root);
	while(!q.empty()){
		root=q.front();q.pop();
		if(root->data==key)
			return root;
		if(root->left)
			q.push(root->left);
		if(root->right)
			q.push(root->right);
	}
	return NULL;
}
int BinaryTree::findElement(BTNode *root,int key){
	int tmp;
	if(root==0)
		return 0;
	else {
		if(root->data==key)
			return 1;
		else {
			tmp = findElement(root->left,key);	
			if(tmp!=0)
				return tmp;
			else findElement(root->right,key);
		}
	}
}
int BinaryTree::findMaxLevelOrder(BTNode *root){
	queue<BTNode*> q;
	int max=INT_MIN;
	q.push(root);
	while(!q.empty()){
		root=q.front();q.pop();
		if(max<root->data)
			max=root->data;
		if(root->left)
			q.push(root->left);
		if(root->right)
			q.push(root->right);

	}
	return max;
}
int BinaryTree::findMax(BTNode *root){
	int max=INT_MIN;
	if(root){
		int t=root->data;
		int max1=findMax(root->left);
		int max2=findMax(root->right);
		if(max1>max2)
			max=max1;
		else max=max2;
		if(max<t)
			max=t;

	}
	return max;
}
void BinaryTree::LevelOrder(BTNode *root){
	queue<BTNode*> q;
	q.push(root);
	while(!q.empty()){
		root=q.front();q.pop();
		cout<<root->data<<' ';
		if(root->left)
			q.push(root->left);
		if(root->right)
			q.push(root->right);
	}
}
void BinaryTree::preorder(BTNode *root){
	if(root){
		cout<<root->data<<' ';
		preorder(root->left);
		preorder(root->right);
	}
}
void BinaryTree::preorderIterative(BTNode *root){
	stack<BTNode*> s;
	s.push(root);
	while (!s.empty()) {
		root = s.top();
		s.pop();
		cout<<root->data<<' ';
		if (root->right)
			s.push(root->right);
		if (root->left)
			s.push(root->left);
	}
}
void BinaryTree::inorderIterative(BTNode *root){
	stack<BTNode*> s;
	BTNode *cur=root;

	bool done=0;
	while(!done){
		if(cur!=NULL){
			s.push(cur);
			cur=cur->left;
		}
		else if(!s.empty()){
			cur=s.top();s.pop();
			cout<<cur->data<<' ';
			cur=cur->right;	
		}
		else done=1;
	}

}


BTNode * BinaryTree::newNode(int key){
	BTNode *tmp=new BTNode;
	tmp->data=key;
	return tmp;
}
void BinaryTree::inorder(BTNode *root){
	if(root)
	{
		inorder(root->left);
		cout<<root->data<<' ';
		inorder(root->right);
	}
}

void BinaryTree::postorderIterative(BTNode *root){
	
	stack<BTNode*> s1, s2;
	s1.push(root);
	while (!s1.empty()) {
		root = s1.top();
		s1.pop();
		s2.push(root);
		if (root->left)
			s1.push(root->left);
		if (root->right)
			s1.push(root->right);
	}
	while (!s2.empty()) {
		root = s2.top();
		s2.pop();
		cout<<root->data<<' ';
	}
}

void BinaryTree::postorder(BTNode *root){
	if(root){
		postorder(root->left);
		postorder(root->right);
		cout<<root->data<<' ';
	}
}
int main(void){


	BinaryTree b;
	BTNode *root2=b.newNode(1);
	root2->left=b.newNode(2);
	root2->right=b.newNode(3);
	root2->left->left=b.newNode(4);
	//root2->left->left->left=b.newNode(14);
	
	root2->left->right=b.newNode(5);
	root2->right->left=b.newNode(6);
	root2->right->right=b.newNode(7);

	BTNode *root=b.newNode(1);
	root->left=b.newNode(2);
	root->right=b.newNode(3);
	root->left->left=b.newNode(4);
	root->left->right=b.newNode(5);
	root->right->left=b.newNode(6);
	root->right->right=b.newNode(7);

	cout<<"\nInorder : ";
	b.inorder(root);
	cout<<"\ninorderIterative : ";
	b.inorderIterative(root);
	cout<<"\npostorder : ";
	b.postorder(root);
	cout<<"\npostOrderIterative : ";
	b.postorderIterative(root);
	cout<<"\npreorder : ";
	b.preorder(root);
	cout<<"\npreOrderIterative : ";
	b.preorderIterative(root);

	cout<<"\nLevel Order : ";
	b.LevelOrder(root);
	
	cout<<"\nMax Element : "<<b.findMaxLevelOrder(root);
	int key=4;
	if(b.findElement(root,key))
	cout<<"\nElement "<<key<<" found";
	else 
		cout<<"\nElement not found";

	
	
	b.insertLevelOrder(root,14);
	cout<<"\nLevel Order : ";
	b.LevelOrder(root);
	
	cout<<"\nSize of Binary Tree : "<<b.sizeOfBinaryTreeLevelOrder(root);
	
	cout<<"\nReverse Level Order : ";
	b.reverseLevelOrder(root);
	//b.deleteBinaryTree(root);//doesn't make root NULL but root points to garbage value

	cout<<"\nHeight : "<<b.heightLevelOrder(root);
	cout<<"\nHeight : "<<b.height(root);

	cout<<"\nDeepest node : "<<b.findDeepestNode(root)->data;

	//b.deleteNode(root,1);//not working need some tweak
	cout<<"\nNumber of Leaves : "<<b.NumberOfLeavesLevelOrder(root);
	cout<<"\nNumber of Full Nodes : "<<b.NumberOfFullNodesLevelOrder(root);
	cout<<"\nNumber of Half Nodes : "<<b.NumberOfHalfNodesLevelOrder(root);
	
		if(b.AreStructurallyIdentical(root,root2))
			cout<<"\nIdentical";
		else cout<<"\nNot Identical";
	

	cout<<"\nDiameter : "<<b.DiameterOfTree(root);	
	cout<<"\nLCA(4,5) : "<<b.findLCA(root,4,5)->data;
	cout<<"\nLCA(4,6) : "<<b.findLCA(root,4,6)->data;


	return 0;
}