simple_tree.cpp

#include<iostream>
#include<queue>
#define NULL __null

class SimpleTree{
public:
    SimpleTree* createNode(const int& data);//return adderss of newly inserted data
    void insertNode(SimpleTree** root, const int& data);//SimpleTree** root, keep track of root
    void printDFS(SimpleTree* root); // for DFS 
    void printBFS(SimpleTree* root); // for BFS
    void searchData(SimpleTree* root, const int& data); // For searching data
private:
    std::queue<SimpleTree*>header; // for keep track of front node in the tree
    int data;
    SimpleTree* left;
    SimpleTree* right;
};

SimpleTree* SimpleTree::createNode(const int& data){
    SimpleTree* temp = new SimpleTree; // memory creation using new opetator
    temp->data = data; //assign data 
    temp->left = nullptr; // assign left child to null 
    temp->right = nullptr; // assign right child to null
    return temp; //return address of newly created node
}

void SimpleTree::insertNode(SimpleTree** root, const int& data) {
    SimpleTree* temp = createNode(data); // here we are calling createNode() for address of node
    if(*root == nullptr){ // if root point to null 
        *root = temp; // then assign root as temp 
        header.push(temp); //and push temp into the queue
    } else{
        SimpleTree* foo = header.front(); //take front node 
        if(foo->left == nullptr){ //check for left child if it is null then 
            foo->left = temp; // assign left child as temp 
            header.push(temp); // push again temp into the queue
        }
        else if(foo->right == nullptr){ // check for right child, if it is pointing to null
            foo->right = temp; // then assign it as temp 
            header.push(temp); // and push temp into the queue
        }
        if(foo->left != nullptr && foo->right != nullptr){ // if foo's both left and right pointer points to null then
            header.pop();//pop front node
        }
    }
}

void SimpleTree::printDFS(SimpleTree *root) { //for DFS we are simply using inorder traversal
    if(root == nullptr){
        return;
    } else{
        printDFS(root->left);
        std::cout << " " << root->data ;
        printDFS(root->right);
    }
}

void SimpleTree::printBFS(SimpleTree *root) {
    if(root == nullptr){
        return;
    } else{
        std::queue<SimpleTree*>bfs;
        bfs.push(root);
        while(!bfs.empty()){
            const SimpleTree* temp = bfs.front();
            if(temp->left != nullptr){
                bfs.push(temp->left);
            }
            if(temp->right != nullptr){
                bfs.push(temp->right);
            }
            std::cout << temp->data << " ";
            bfs.pop();
        }
    }
}
void  SimpleTree::searchData(SimpleTree *root, const int& data) {
    if(root == nullptr){
        return;
    } else{
        searchData(root->left, data);
        if(root->data == data){
            std::cout << "Data found in the tree.\n";
            return;
        }
        searchData(root->right, data);
    }
}

int main(){
    SimpleTree* root = nullptr, st;
    char ch = 'y';
    int data;
    do{
        std::cout << "Enter data? ";std::cin >> data;
        st.insertNode(&root, data);
        std::cout << "Do you want to continue(y/n) ?";
        std::cin >> ch;
    }while(ch != 'n');
    std::cout << "DFS: ";
    st.printDFS(root);
    std::cout << "\nBFS: ";
    st.printBFS(root);
    std::cout << "\nEnter data which you want to search ?";
    std::cin >> data;
    st.searchData(root, data);
}