Binary Tree

Binary Tree is very famous data structure. Left of the parent node has smaller than parent’s value and right is bigger. In this code I’ll give a simple demonstration of binary tree (implemented in C++ but knowing C is enough to get the idea). Although code is self explanatory I’ll give important highlights.

#include <iostream>

using namespace std;

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

enum Order {
    InOrder,
    PreOrder,
    PostOrder
};

Node* root = NULL;

Node* create_node(int val)
{
    Node* n = new Node;
    n->val = val;
    n->left = n->right = NULL;

    return n;
}

void add_node(Node* curr, Node* node)
{
    if (root == NULL) { // empty tree, we're adding root
        root = node;
    }
    else {
        if (curr->val > node->val) {
            if (curr->left == NULL)
                curr->left = node;
            else
                add_node(curr->left, node);
        }
        else {
            if (curr->right == NULL)
                curr->right = node;
            else
                add_node(curr->right, node);
        }
    }

}

void display_btree(Node* node, Order order)
{
    if (order == InOrder)
        cout << node->val << endl;

    if (node->left)
        display_btree(node->left, order);

    if (order == PreOrder)
        cout << node->val << endl;

    if (node->right)
        display_btree(node->right, order);

    if (order == PostOrder)
        cout << node->val << endl;
}

int main() {
    root = create_node(50);
    Node* n1 = create_node(30);
    Node* n2 = create_node(70);
    Node* n3 = create_node(10);
    Node* n4 = create_node(40);
    Node* n5 = create_node(60);
    Node* n6 = create_node(80);

    add_node(root, n1);
    add_node(root, n2);
    add_node(root, n3);
    add_node(root, n4);
    add_node(root, n5);
    add_node(root, n6);

    display_btree(root, InOrder);

    return 0;
}

The code is recursive. It recursively finds out the node for insertion. Binary trees can be shown with Pre-order, In-order and Post-order manner. display_btree function recursively displays the nodes with the selected method.