# Why Cannot Find deepest node in Binary search tree 28,22,23,19,21,125 ?

• #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()
//void BST<T>::deepestNodes2(BTNode<T> *, T & );

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
//	struct Node *left, *right;

// 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

//other useful functions for BST
bool display(int, int);
bool search(int, T &);
bool deepestNode();
bool printSubtree(T);
bool clear();
``````

};

template <class T>
bool BST<T>::clear()
{

}

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

}

//====================The function is here, it is any problem why cannot print out deepest node from tree========================/////
template <class T>
bool BST<T>::deepestNode()
{
BTNode<T> *cur;

``````if (empty()) return false;

if(countNode()==NULL)
cout << cur->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>
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));
}

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

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.