// Syed Rais Ahmad
//Assignment 6 Ans 1
//Number of nodes , Sum of content of nodes.

#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);
	Tree(Tree&);
	~Tree();
	bool IsSimilar(Tree*);
	bool IsStrictBinary();
	int TotalNodes();
	bool IsLeaf(btNode*);
	int SetLeft(btNode*,int);
	int SetRight(btNode*,int);
	int SumOfNodes();

	
	bool IsEmpty();
	btNode* GetRoot();
	btNode* Left(btNode*);
	btNode* Right(btNode*);
	btNode* Father(btNode*);
	int SumNode(btNode*);
	int TotalNode(btNode*);
	int  pr(btNode*);
	int Depth(btNode*,int);
	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;
}


btNode * Tree::Father(btNode * node)
{
	if (node==root->left) return NULL;
	return node;
}


Tree::~Tree()
{
	delete root;
}

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

btNode * Tree::Left(btNode * node)
{
	return node->left;
}


btNode * Tree::Right(btNode * node)
{
	return node->right;
}

//print the values in tree
int Tree::pr(btNode * node)
{
	if (node)
	{
		cout << node->info;
		pr(node->left);
		pr(node->right);
	}
	return 0;

}

int Tree::TotalNode(btNode * node)
{
	if (node)
		return TotalNode(node->right) + TotalNode(node->left)+1;
	else
		return 0;
}



int Tree::SumNode(btNode * node)
{
	if (node)
		return SumNode(node->left)+SumNode(node->right)+node->info;
	else
		return 0;
}

int Tree::Depth(btNode* node,int n)
{
	int i=0,j=0;
	if (node && (node->right || node->left))
	{
		i=Depth(node->left,n+1);
		j=Depth(node->right,n+1);
		return (i>j)? i:j;
	}
	else if (!node) return n-1;
	else
		return n;

}



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

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

	t.SetLeft(tmp,2);
	t.SetRight(tmp,3);
	tmp2=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);
	//t.SetRight(tmp,9);
	
	
t.pr(t.GetRoot());
 cout << '\n'<< t.SumNode(t.GetRoot());
 cout << '\n' << t.TotalNode(t.GetRoot());
 cout << '\n' << t.DepthofNode(t.GetRoot(),t.Left(t.GetRoot()),0);

	return 0;
}