For RC

DFS on BT

#include <iostream>
#include <iomanip>
#include <stack> 
using namespace std; 


class Tree{

public:
	//create each node
	struct node {
		int data;
		node *left; 
		node *right; 
	};

	//constractor
	Tree(){
		root=NULL;
	}

	//insert data
	void insert(int key){
		if(root!=NULL){
			insert(key, root);
		}else{
			
			node *r = new node();
			r->data = key; 
			r->left = NULL;
			r->right= NULL;
			root = r;
		}
	}

	//used to call the 'private' dfs
	int dfs(int num){
		int res =dfs(root, num);
		return res;
	}

	//used to call the 'private' print
	void print(){
		print(root);
	}
	
private:

	node *root;
	//insert nodes in BST
	void insert(int key, node*child){
		if(key<child->data){
			if(child->left!=NULL){
				insert(key, child->left);
			}else{
				child->left = new node();
				child->left->data = key;
				child->left->left =NULL;
				child->left->right=NULL;
			}
		}
		else if(key>=child->data){
			if(child->right!=NULL){
				insert(key, child->right);
			}else{
				child->right = new node();
				child->right->data = key;
				child->right->left = NULL;
				child->right->right =NULL;
			}
		}
	}

	//print the tree
	void print(node *leaf, int indent =0){

		// if(r!=NULL){
		// 	cout<<endl;
		// 	cout<<r->data; 
		// 	cout<<"  left: ";
		// 	print(r->left);
		// 	cout<<" right: ";
		// 	print(r->right);
		// }
		
		if(leaf!=NULL){
			if(leaf->right){
				print(leaf->right, indent+4);
			}
			if(indent){
				cout<<setw(indent)<<' ';
			}
			if(leaf->right)
				cout<<" /\n"<<setw(indent)<<' ';
			cout<<leaf->data<< "\n";
			if(leaf->left){
				cout<<setw(indent)<<' '<<" \\\n";
				print(leaf->left, indent+4);
			}
		}
	}

	//search in dfs
	int dfs(node* root, int num){
		stack <node*> stack;
		stack.push(root);
		while(!stack.empty()){
			node *cur = stack.top();
			stack.pop();
			if(cur->data==num){
				cout<<"Found the number!: ";
				return num;
			}
			if(cur->left !=NULL){
				stack.push(cur->left);
			}
			if(cur->right != NULL){
				stack.push(cur->right);
			}

		}
		cout<<"Number is not found: ";
		//Null is a type of *void in C++ so cant return it as an int
		return 0;
	}
};


int main(){
	Tree a; 
	a.insert(2);
	a.insert(6);
	a.insert(7);
	a.insert(5);
	a.insert(4);
	a.insert(3);
	a.insert(2);
 
 	int output = a.dfs(33);
 	cout<<output;
 	//a.print();
    return 0;


}