// Syed Rais Ahmad
//Assignment # 6 Answer 2
//Is tree strictly binary?



#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 * IsStrictBinary(btNode*,bool*);
	bool IsLeaf(btNode*);
	int SetLeft(btNode*,int);
	int SetRight(btNode*,int);
	bool IsEmpty();
	btNode* GetRoot();
	int  pr(btNode*);
};


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::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;
}

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

}


bool * Tree::IsStrictBinary(btNode * node,bool *flag)
{
	if (node && *flag)
	{
		IsStrictBinary(node->left,flag);
		if (node->left && !node->right) *flag=false;
		if (!node->left && node->right) *flag=false;
		IsStrictBinary(node->right,flag);
	}
	return flag;
}


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

	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;
	bool b=true;
	if (*(t.IsStrictBinary(t.GetRoot(),&b))) cout << "Tree is Strictly Binary\n";
	else
		cout << "\nTree is not binary";

	return 0;
}