Interview Question: Find the deepest node in a binary tree

(1)
#include<iostream>
#include<queue>

using namespace std;

struct Node{
    int data;
	Node* left, *right;
    Node(){ data=-1; }
    Node(int value):data(value),left(nullptr),right(nullptr){}
};

class bst_tree{
public:
	bst_tree(){ root = nullptr; }
	void insert(int num) { insert(root, num); }
	Node *get_deepest_node(Node* );
	Node *getRoot();
private:
	Node* root;
    void insert(Node *&, int);
};

Node* bst_tree::get_deepest_node(Node* rt){
	if(rt==nullptr)
		return nullptr;
	queue qnode;
	qnode.push(rt);
	Node* tmp=nullptr;
	while(!qnode.empty()){
		tmp = qnode.front();
		qnode.pop();
		if(tmp->left) qnode.push(tmp->left);
		if(tmp->right) qnode.push(tmp->right);
	}
    			temp = temp->left;
		else
			temp = temp->right;
	}
	if(!q) q = new Node(num);
	else{
		if(num < prev->data)
			prev->left = new Node(num);
		else
			prev->right = new Node(num);
	}
}

Node* bst_tree::getRoot(){
    return root;
}

int main(){
	
	bst_tree bst;
	bst.insert(1);
	bst.insert(2);
	bst.insert(3);
	bst.insert(4);
        Node* tree_root = bst.getRoot();
        cout<<tree_root->data<<endl;
        Node* d = bst.get_deepest_node(tree_root);
        cout<<"the deepest node is :"<<d->data<<endl;
	return 0;
}

(2)
#include<iostream>
#include<queue>

using namespace std;

template <typename T>
struct Node{
	Node *leftchild, *rightchild;
	T data;
};

template <typename T>
class BinarySearchTree{
public:
    BinarySearchTree(){ rootNode=nullptr;};
    void insert(T);
	void search(T);
    Node* get_deepest_node(Node* );
private:


	Node *rootNode;
};

template<typename T>
void BinarySearchTree::insert(T newNum){
	cout<<"e;Insert: "e;<<newNum<<endl;
	Node *newNode = new Node;

	newNode->data = newNum;
	newNode->leftchild = newNode->rightchild = nullptr;

	Node * prev = nullptr;
	if(rootNode == nullptr)
		rootNode = newNode;
	else{
		Node *current =  rootNode;

		while(current){
			prev = current;
			if(newNode -> data <= current -> data)
				current = current -> leftchild;
			else
				current = current -> rightchild;
		}

		if(newNode -> data <= prev->data)
			prev -> leftchild = newNode;
		else
			prev -> rightchild = newNode;
	}
}

template<typename T>
void BinarySearchTree::search(T toFindNum){
	Node *current = rootNode;
//	Node *parent = rootNode;
	bool rootflag = false;
	if(current->data == toFindNum){
		rootflag = true;
		cout<<"e;Found the element, it is root."e;<<endl;
	}
    else{
    	while(current && current -> data != toFindNum){
    		//parent = current;
    		if(current -> data >= toFindNum)
    			current = current -> leftchild;
    		else
    			current = current -> rightchild;
    	}
    	if(current && !rootflag)
    		cout<<"Found the element!"<<endl;
        else
            cout<<"e;Couldn't find the element"e;<<endl;
    }
}

template<typename T>
Node* BinarySearchTree::get_deepest_node(Node* root){
    if(root==nullptr)
        return nullptr;
    queue*> qnode;
    qnode.push(root);
    
    Node* current;
    while(!qnode.empty()){
        current = qnode.front();
        qnode.pop();
        if(current->left) qnode.push(current->left);
        if(current->right) qnode.push(current->right);
    }
    return current;
}

int main(){
	BinarySearchTree b;
	b.insert(7);
        b.insert(5);
        b.insert(11);
	b.search(10);

	BinarySearchTree c;
	c.insert('k');
	c.search('v');

	return 0;
}