Question

Create a binary search tree in C++, where it will have an add_node(int i) function which when called in the main (i.e. add_node(5)) it will add it to the tree. This tree will also place the nodes added in the correct order (if the head node is 40, all the nodes that are added that are less than 40 go to the left of the tree, and all the nodes larger than 40 go to the right)

Also add a function that can traverse the tree, either on the left branch or the right branch.

Answer 1

#include <iostream>
using namespace std;

class bst {
private:
    class node {
    public:
        int value;
        node *left;
        node *right;
    };

    node *root;
    void add_node(node *&temp, node *n) {
        if(temp == nullptr) {
            temp = n;
        } else if(n->value < temp->value) {
            add_node(temp->left, n);
        } else {
            add_node(temp->right, n);
        }
    }
    void print(node *temp) {
        if(temp) {
            print(temp->left);
            cout << temp->value << " ";
            print(temp->right);
        }
    }
public:
    bst() {
        root = nullptr;
    }
    void add_node(int num) {
        node *n = new node;
        n->value = num;
        n->left = nullptr;
        n->right = nullptr;
        add_node(root, n);
    }
    void print() {
        print(root);
        cout << endl;
    }
};

int main() {
    bst tree;
    tree.add_node(5);
    tree.add_node(2);
    tree.add_node(9);
    tree.add_node(6);
    tree.add_node(1);
    tree.add_node(7);
    tree.print();
    return 0;
}