//Syed Rais Ahmad
//Assignment # 6 Ans 5
//given node pointer, return its level in tree.

#include "stdafx.h"

#include<iostream.h>
#include<assert.h>
class btNode
{
public:
	int info;
	btNode * left;
	btNode * right;
};

class Tree 
{
private:
	btNode * root;
public:
	Tree(); 
	Tree(int);
	bool IsLeaf(btNode*);
	int SetLeft(btNode*,int);
	int SetRight(btNode*,int);
	bool IsEmpty();
	btNode* GetRoot();
	int DepthofNode(btNode*,btNode*,int);
};


Tree::Tree()
{
	root=new btNode;
	root->left=NULL;
	root->right=NULL;
}

//init tree with root node having info=n
Tree::Tree(int n)
{
	root=new btNode;
	root->left=new btNode;
	root->right=NULL;
	root->left->left=root->left->right=NULL;
	root->left->info=n;
}

bool Tree::IsLeaf(btNode * p)
{
	return (!p->left && !p->right)? true : false;
}

bool Tree::IsEmpty()
{
	return (root->left && root->right)? false : true;

}

int Tree::SetLeft(btNode * parent,int n)
{
	if (!root->left)
	{
		root->left=new btNode;
		root->left->info=n;
		root->left->left=root->left->right=NULL;
		return n;
	}
	else 
	{
		parent->left=new btNode;
		parent->left->info=n;
		parent->left->left=parent->left->right=NULL;
		return n;
	}
	return -1;
}


int Tree::SetRight(btNode * parent,int n)
{
	if (!root->left)
	{
		root->right=new btNode;
		root->right->info=n;
		root->right->left=root->right->right=NULL;
		return n;
	}
	else 
	{
		parent->right=new btNode;
		parent->right->info=n;
		parent->right->left=NULL;
		parent->right->right=NULL;
		return n;
	}
	return -1;
}


//Return the root's address
btNode * Tree::GetRoot()
{
	if (root->left) return root->left;
	else return NULL;
}

int Tree::DepthofNode(btNode* node,btNode* nd,int n)
{
	int i,j;i=j=-1;
	if (node)
	{
		if (node==nd) return n;
		else
		{
			i=DepthofNode(node->left,nd,n+1);
			j=DepthofNode(node->right,nd,n+1);
		}
		return (i==j)? i : (i>j)? i: j;

	}
}


//main program starts here.
main()
{
	Tree t(1);
	
	btNode * tmp=t.GetRoot(),* temp;

	t.SetLeft(tmp,2);
	t.SetRight(tmp,3);
	tmp=tmp->left;

	t.SetLeft(tmp,4);
	t.SetRight(tmp,5);
	
	tmp=t.GetRoot();
	tmp=tmp->right;
		
	t.SetLeft(tmp,6);
	t.SetRight(tmp,7);
	tmp=tmp->left;
	t.SetLeft(tmp,8);
	temp=tmp->left;

	cout << '\n' << t.DepthofNode(t.GetRoot(),temp,0);
	tmp=t.GetRoot();
	tmp=tmp->left;
	cout << '\n' << t.DepthofNode(t.GetRoot(),tmp,0);


	return 0;
}