Subtree and deepest node

[kaizen]

I got 2 problem in my bst coding.
1. I knw how to find the deepest node using the height of the tree and print out the node but now i need to change it become print out all the deepest node and how to do so? bool BST<T>::deepestNodes()

2. Print subtree, i knw how to print whole tree but for subtree how? bool BST<T>::printSubtree(T item)

[kaizen]

#ifndef BT_type
#define BT_type

#include	"BTNode.h"
#include	"Queue.h"
#include    <fstream>

using namespace std;

template <class T>
class BST {
	private:
		int			count;
		BTNode<T>	*root;

		// print operation for BST (same as BT)					
		void preOrderPrint2(BTNode<T> *);	// recursive function for preOrderPrint()
		void inOrderPrint2(BTNode<T> *);	// recursive function for inOrderPrint()
		void postOrderPrint2(BTNode<T> *);	// recursive function for postOrderPrint()


		// sample operation (extra functions) - same as BT
		void countNode2(BTNode<T> *, int &);		// recursive function for countNode()
		bool fGS2(T, BTNode<T> *);					// recursive function for findGrandsons(): to find the grandfather
		void fGS3(BTNode<T> *, int);				// recursive function for findGrandsons(): to find the grandsons after the grandfather has been found
		
		// basic functions for BST
		void insert2(BTNode<T> *, BTNode<T> *);		// recursive function for insert() of BST
		void case3(BTNode<T> *);					// recursive function for remove()
		void case2(BTNode<T> *, BTNode<T> *);		// recursive function for remove()
		bool remove2(BTNode<T> *, BTNode<T> *, T);	// recursive function for remove()

		
	public:
		// basic functions for BST
		BST();
		bool empty();
		int size();
		bool insert (T);		// insert an item into a BST
		bool remove(T);			// remove an item from a BST
		
		// print operation for BST (same as BT)
		void preOrderPrint();			// print BST node in pre-order manner
		void inOrderPrint();			// print BST node in in-order manner
		void postOrderPrint();			// print BST node in post-order manner
		void topDownLevelTraversal();	// print BST level-by-level

		// sample operation (extra functions) - same as BT
		int countNode();		// count number of tree nodes
		bool findGrandsons(T);	// find the grandsons of an input father item

		bool display(int, int);
		bool printSubtree(T); 
		bool deepestNode();
		bool printAncestor(T);
		bool clear();
		
		
		
};


template <class T>
bool BST<T>::printAncestor(T item)
{
	/* base cases */
	if (root == NULL)
		return false;

	if (root->data == target)
		return true;

	/* If target is present in either left or right subtree of this node,
	then print this node */
	if (printAncestors(root->left, target) ||
		printAncestors(root->right, target))
	{
		cout << root->data << " ";
		return true;
	}

	/* Else return false */
	return false;
}


template <class T>
bool BST<T>::clear()
{
	if (root == NULL)
	{
		cout << "Empty" << endl;
		return false;
	}

	else
	{
		clearNodes(root);
		root = NULL;
		return true;
	}

}


template <class T>
bool BST<T>::deepestNode()
{
	
}


template <class T>
bool BST<T>::printSubtree(T item) 
{
	
}


template <class T>
BST<T>::BST() {
	root = NULL;
	count = 0;
}

template <class T>
bool BST<T>::empty() {
	if (count==0) return true;
	return false;
}

template <class T>
int BST<T>::size() {
	return count;
}


template <class T>
void BST<T>::preOrderPrint() {
	if (root == NULL) 
	{
		cout << "\nEmpty tree\n";
		return;// handle special case
	}
	else preOrderPrint2(root);// do normal process
	cout << endl;
}

template <class T>
void BST<T>::preOrderPrint2(BTNode<T> *cur) {
	if (cur == NULL) return;
	cout << cur->item << ' '; 
	preOrderPrint2(cur->left);
	preOrderPrint2(cur->right);
}

template <class T>
void BST<T>::inOrderPrint() {
	if (root == NULL) return;// handle special case
	else inOrderPrint2(root);// do normal process
	cout << endl;
}

template <class T>
void BST<T>::inOrderPrint2(BTNode<T> *cur) {
	if (cur == NULL) return;
	inOrderPrint2(cur->left);
	cout << cur->item << ' '; 
	inOrderPrint2(cur->right);
}

template <class T>
void BST<T>::postOrderPrint() {
	if (root == NULL) return;// handle special case
	else postOrderPrint2(root);// do normal process
	cout << endl;
}

template <class T>
void BST<T>::postOrderPrint2(BTNode<T> *cur) {
	if (cur == NULL) return;
	postOrderPrint2(cur->left);
	postOrderPrint2(cur->right);
	cout << cur->item << ' '; 
}


template <class T>
int BST<T>::countNode() {
	int	counter=0;
	if (root==NULL) return 0; 
	countNode2(root, counter);   
	return counter;
}

template <class T>
void BST<T>::countNode2(BTNode<T> *cur, int &count) {
	if (cur == NULL) return;
	countNode2(cur->left, count);
	countNode2(cur->right, count);
	count++;
}

template <class T>
bool BST<T>::findGrandsons(T grandFather) {
	if (root==NULL) return false;
	return (fGS2(grandFather, root));   
}

[kaizen]

template <class T>
bool BST<T>::fGS2(T grandFather, BTNode<T> *cur) {
	if (cur == NULL) return false;
	if (cur->item == grandFather) {
		cout << endl << "Grandfather " << cur->item << " has grandsons" << endl;
		fGS3(cur, 0); // do another TT to find grandsons
		return true;
	}
	if (fGS2(grandFather, cur->left)) return true;
	return fGS2(grandFather, cur->right);
}

template <class T>
void BST<T>::fGS3(BTNode<T> *cur, int level) {
	if (cur == NULL) return;
	if (level==2) {
		cout << '\t' << cur->item;
		return;  // No need to search downward
	}
	fGS3(cur->left, level+1);
	fGS3(cur->right, level+1); 
}

template <class T>
void BST<T>::topDownLevelTraversal() {
	BTNode<T>			*cur;
	Queue<BTNode<T> *>	q;

	if (empty()) return; 	// special case
	q.enqueue(root);	// Step 1: enqueue the first node
	while (!q.empty()) { 	// Step 2: do 2 operations inside
		q.dequeue(cur);
		if (cur != NULL) {
			cout << cur->item << ' ';
			if (cur->left != NULL) q.enqueue(cur->left);
			if (cur->right != NULL) q.enqueue(cur->right);
		}
	}
}

template <class T>
void BST<T>::insert2(BTNode<T> *cur, BTNode<T> *newNode) { 
	if (cur->item > newNode->item) {
		 if (cur->left == NULL) 
			 cur->left = newNode;
		 else 
			 insert2(cur->left, newNode);
	}
	else {
		 if (cur->right == NULL) 
			 cur->right = newNode;
		 else 
			 insert2(cur->right, newNode);
	}
} 

//insert for BST
template <class T>
bool BST<T>::insert(T newItem) {
	BTNode<T>	*cur = new BTNode<T>(newItem);
	if (!cur) return false;		// special case 1
	if (root==NULL) {
		root = cur;
		count++;
		return true; 			// special case 2
	}
	insert2(root, cur);			// normal
	count++;
	return true;
}

template <class T>
void BST<T>::case3(BTNode<T> *cur) {
	BTNode<T>		*is, *isFather;			
	
	// get the IS and IS_parent of current node
	is = isFather = cur->right;				
	while (is->left!=NULL) {				
		isFather = is;
		is = is->left;
	}

	// copy IS node into current node
	cur->item = is->item;

	// Point IS_Father (grandfather) to IS_Child (grandson)
	if (is==isFather) 
		cur->right = is->right;		// case 1: There is no IS_Father    
	else 
		isFather->left = is->right;	// case 2: There is IS_Father
	
	// remove IS Node
	free(is);								
}


template <class T>
void BST<T>::case2(BTNode<T> *pre, BTNode<T> *cur) {

	// special case: delete root node
	if (pre==cur) {	
		if (cur->left!=NULL)	// has left son?
			root = cur->left; 
		else 
			root = cur->right;

		free(cur);
		return;
	}
	
	if (pre->right==cur) {		// father is right son of grandfather? 
		if (cur->left==NULL)			// father has no left son?
			pre->right = cur->right;			// connect gfather/gson
		else 
			pre->right = cur->left;
	}
	else {						// father is left son of grandfather?
		if (cur->left==NULL)			// father has no left son? 
			pre->left = cur->right;				// connect gfather/gson
		else 
			pre->left = cur->left;
	}

	free(cur);					// remove item
}


template <class T>
bool BST<T>::remove2(BTNode<T> *pre, BTNode<T> *cur, T item) { 
	
	// Turn back when the search reaches the end of an external path
	if (cur == NULL) return false;

	// normal case: manage to find the item to be removed
	if (cur->item == item) {
		if (cur->left == NULL || cur->right == NULL) 
			case2 (pre, cur);	// case 2 and case 1: cur has less than 2 sons
		else 
			case3 (cur);		// case 3, cur has 2 sons
		count--;				// update the counter
		return true;
	}

	// Current node does NOT store the current item -> ask left sub-tree to check
	if (cur->item > item)
		return remove2(cur, cur->left, item);
	
	// Item is not in the left subtree, try the right sub-tree instead
	return remove2(cur, cur->right, item);
}

template <class T>
bool BST<T>::remove(T item) {
   	if (root == NULL) return false; 		// special case 1: tree is empty
   	return remove2(root, root, item); 		// normal case
}


#endif