Binary Search Tree Example

main.cpp

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <iostream>

template <typename T> struct Node {
    bool filled;
    T data;
    Node* left;
    Node* right;

    void insert(T data) {
        Node<T>* temp = (Node<T>*) calloc(1, sizeof(Node<T>));

        temp->data = data;

        if (!this->filled) {
            this->data = data;
            this->filled = true;
        } else {
            Node<T>* current = this;
            Node<T>* parent  = NULL;

            while (1) {
                parent = current;

                if (data < parent->data) {
                    current = current->left;

                    if (current == NULL) {
                        parent->left = temp;
                        break;
                    }
                } else {
                    current = current->right;

                    if (current == NULL) {
                        parent->right = temp;
                        break;
                    }
                }
            }
        }
    }
};

template <typename T> void inorder_traversal(Node<T>* root) {
    if (root) {
        inorder_traversal(root->left);
        printf("%d ", root->data);
        inorder_traversal(root->right);
    }
}

int main() {
    typedef uint32_t T;
    
    Node<T>* root = (Node<T>*) calloc(1, sizeof(Node<T>)); 
    
    root->insert(50);
    root->insert(40);
    root->insert(60);
    root->insert(30);
    root->insert(45);
    root->insert(70);

    inorder_traversal(root);

    std::cout << std::endl;

    return 0;
}