Implementation of Binary Search Tree

To understand the implementation of a binary search tree using C++

Objective

To understand the implementation of a binary search tree using structures using C++

#include <iostream>
using namespace std;

struct Node {
    int val;
    Node* left;
    Node* right;
};

Node* createNode(int val) {
    Node* newNode = new Node();
    if (!newNode) {
        cout << "Memory allocation failed";
        return NULL;
    }
    newNode->val = val;
    newNode->left = newNode->right = NULL;
    return newNode;
}

Node* insertNode(Node* root, int val) {
    if (root == NULL) {
        root = createNode(val);
        return root;
    }

    if (val < root->val)
        root->left = insertNode(root->left, val);

    else if (val > root->val)
        root->right = insertNode(root->right, val);

    else 
        cout << "Duplicate value! Node not added." << endl;

    return root;
}

void printInOrder(Node* root) {
    if (root == NULL)
        return;
    printInOrder(root->left);
    cout << root->val << " ";
    printInOrder(root->right);
}

int main() {
    Node* root = NULL;
    root = insertNode(root, 10);
    insertNode(root, 20);
    insertNode(root, 30);
    insertNode(root, 15);
    insertNode(root, 5);

    printInOrder(root);
    return 0;
}

Discussion of Algorithm

1. Start.
2. Create a new node with the value.
3. Check if the tree is empty. If it is, the new node is the root.
4. If the tree is not empty, compare the new value with the current node value.
5. If the new value is less than the current node value, go to the left child. If the left child is null, insert here. If not, repeat step 4.
6. If the new value is greater than the current node value, go to the right child. If the right child is null, insert here. If not, repeat step 4.
7. If the new value is equal to the current value, return an error or simply ignore.
8. End.

Representations

Flow Diagram

   +----------------------------------+
   |                                  |
   |            Start                 |
   |              |                   |
   +----------------------------------+
                  |
                  V
   +----------------------------------+
   |                                  |
   |         Node* root               |
   |              |                   |
   +----------------------------------+
                  |
                  V
   +----------------------------------+
   |                                  |
   |  root = insertNode(root, 10);    |
   |              |                   |
   +----------------------------------+
                  |
                  V
   +----------------------------------+
   |                                  |
   |    insertNode(root, 20);         |
   |    insertNode(root, 30);         |
   |    insertNode(root, 15);         |
   |    insertNode(root, 5);          |
   |              |                   |
   +----------------------------------+
                  |
                  V
   +----------------------------------+
   |                                  |
   |        printInOrder(root)        |
   |              |                   |
   +----------------------------------+
                  |
                  V
   +----------------------------------+
   |                                  |
   |            Exit                  |
   |             |                    |
   +----------------------------------+

Tabular Dry Run

Output

5 10 15 20 30