binarySearchTree.cpp

#include <iostream>

using namespace std;

struct node {
    int key;
    node *left;
    node *right;
    node *parent;
    
    node(int _key) : key(_key), left(NULL), right(NULL), parent(NULL) {}
};

void insert(node *n, int x) {
    if (x < n->key) {
        if (n->left == NULL) {
            node *temp = new node(x);
            n->left = temp;
            temp->parent = n;
        } else {
            insert(n->left, x);
        }
    } else {
        if (n->right == NULL) {
            node * temp = new node(x);
            n->right = temp;
            temp->parent = n;
        } else {
            insert(n->right, x);
        }
    }
}

void preOrder(node *n) {
    cout << n->key << endl;
    if (n->left) {
        preOrder(n->left);
    }
    if (n->right) {
        preOrder(n->right);
    }
}

string description(node *n) {
    string s = "";
    
    if (n->left) {
        s += "(" + description(n->left) + ") <- ";
    }
    s += to_string(n->key);
    if (n->right) {
        s += " -> (" + description(n->right) + ")";
    }
    
    return s;
}

node* search(node *n, int x) {
    
    if (x < n->key) {
        if (n->left) {
            return search(n->left, x);
        }
    } else if (x > n->key) {
        if (n->right) {
            return search(n->right, x);
        }
    } else {
        return n;
    }
    return NULL;
    
};

int main(int argc, const char * argv[]) {
    
    node * root = new node(7);
    
    insert(root, 2);
    insert(root, 5);
    insert(root, 10);
    insert(root, 9);
    insert(root, 1);
    
    cout << description(root) << endl;
    
    cout << search(root, 6) << endl;
    cout << search(root, 5)->key << endl;
    
    return 0;
}