Exercise P12.6.

Solution

#include < iostream>

using namespace std;

class TreeNode {
public:
    void insert_node(TreeNode* new_node){
        if(new_node->data < data){
            if(left==NULL){
                left = new_node;
            }else{
                left->insert_node(new_node);
            }
        } else if(new_node->data > data){
            if(right==NULL){
                right = new_node;
            }else{
                right->insert_node(new_node);
            }
        } 
        else {
            if(left == NULL){
                left = new_node;
            }else{
                new_node->left = left;
                left = new_node;
            }
        }
    }

    void print_node() const{
        if(left != NULL) left->print_node();
        cout << data << endl;
        if(right != NULL) right->print_node();      
    }

    bool find_node(int value) const{
        if(value < data){
            if(left == NULL){
                return false;
            }else{
                return left->find_node(value);
            }
        }else if(value > data){
            if(right == NULL){
                return false;
            }else{
                return right->find_node(value);
            }
        }
        return true;
    }
    
private:
    int data;
    TreeNode* left;
    TreeNode* right;
friend class BinarySearchTree;
};

class BinarySearchTree{
public:
    BinarySearchTree(){
        root = NULL;
    }
    void insert(int data){
        TreeNode* new_node = new TreeNode;
        new_node->data = data;
        new_node->left = NULL;
        new_node->right= NULL;

        if(root == NULL){
            root = new_node;
        }else{
            root->insert_node(new_node);
        }
    }

    void print() const{
        if(root != NULL){
            root->print_node();
        }
    }

    void find(int value) const{
        bool check = false;
        if(root == NULL){
            check = false;
        }else{
            check = root->find_node(value);
        }

        if(check) cout << "Found it!" << endl;
        else cout<< "Nope!" << endl;
    }
private:
    TreeNode* root;
};

int main(){

    BinarySearchTree t;

    t.insert(5);
    t.insert(2);
    t.insert(7);
    t.insert(3);
    t.insert(4);
    t.insert(8);
    t.insert(7);
    t.insert(6);

    t.print();

    t.find(5); // Found it!
    t.find(11); // Nope!
    t.find(7); // Found it!
}