Binary Trees using C++

A tree is a hierarchical data structure and a tree where each node has a maximum of two child nodes is called a Binary Tree.

Trees provide moderate insertion / deletion times which is quicker than arrays but slower than unordered linked lists. Unlike arrays, trees and linked lists both don't have an upper limit on the number of nodes as nodes are linked using pointers.

Some Properties of Binary Trees

The maximum number of nodes at level 'l' of a binary tree is 2^l and nodes at the next level is, 2*2^l or 2^(l+1).
The maximum number of nodes in a binary tree of height 'h' is 2^h - 1.
In a binary tree with N nodes, minimum possible height or the minimum number of levels is Log2(N+1).
A binary tree with L leaves has at-least |Log2L| + 1 levels.
Number of leaf nodes is one more than the number of nodes with two children.

Types of B-Trees

Full Binary Trees -> Every node has 0 or 2 child nodes.
Complete Binary Trees -> Every level is completely filled except the last level and the last level has all nodes (leaf nodes) as left as possible.
Perfect Binary Trees -> All internal nodes have two child nodes and all leaf nodes are at the same level.
Balances Binary Trees -> A Binary tree where the height of the left and the right sub-tree differs by at most 1 level. Also both the left and right sub-trees are balanced. Balanced Binary Trees are good performance wise as they provide O(LogN) time for search, insert and delete operations.
Degenerate ( or pathological) tree -> Every internal node has one child. Same performance as Linked Lists.

Implementing B-Tree in C++

In my demonstration I would be using struct rather than classes.

struct Node{
    int data;
    struct Node* left;
    struct Node* right;

    Node(int data){
        this->data = data;
        left = NULL;
        right = NULL;
    }
};

Insertion in a B-Tree

struct Node* insertion(struct Node* root, int value){
    if(root==NULL){
        root = new Node(value);
        return root;
    }
    else{
        queue<struct Node*> q;
        q.push(root);
        while(!q.empty()){
            struct Node* temp = q.front();
            q.pop();
            if(temp->left){
                q.push( temp->left );
            }
            else if( temp->left == NULL ){
                temp->left = insertion(temp->left, value);
                return root;
            }

            if(temp->right){
                q.push( temp->right );
            }
            else if( temp->right == NULL ){
                temp->right = insertion(temp->right, value);
                return root;
            }
        }
    }
    return root;
}

We create a recursive function where we start by filling the root node first. If the root node is not empty we start traversing through the tree to find the next empty spot for insertion.

For traversal we can create a queue where we add the children of the current node to the queue and then iteratively traverse through the queue till we find an empty position for insertion.

Deletion in a B-Tree

In order to delete a node from B-Tree we need to make sure that the tree shrinks from the bottom.

Algorithm :-

Starting from the root find the deepest and the rightmost node in the binary tree.

Find the node that needs to be deleted and replace its value with the deepest and the rightmost node

Delete the deepest and the rightmost node.

int delete_deepest_right(struct Node*& root){
    int result;
    queue<struct Node*> q;
    q.push(root);
    struct Node* parent = root;
    while(!q.empty()){
        struct Node* temp = q.front();
        q.pop();
        if(temp->left){
            q.push(temp->left);
            parent = temp;
            }
        if(temp->right){
            q.push(temp->right);
            parent = temp;
            }
    }
    if(parent->right){
        result = parent->right->data;
        parent->right = NULL;
    }
    else if(parent->left){
        result = parent->left->data;
        parent->left = NULL;
    }
    return result;
}

In the function above we traverse the entire tree in order to find the parent node of the deepest and the rightmost node. We also store the value of that node so that it can be used by the deletion function below.

struct Node* deletion(struct Node* root,int val){
    if(root==nullptr)
        return root;
    queue<struct Node*> q;
    q.push(root);
    while(!q.empty()){
        struct Node* temp = q.front();
        q.pop();
        if(temp->left){q.push(temp->left);}
        if(temp->right){q.push(temp->right);}
        if(temp->data==val && temp==root && root->left==NULL && root->right==NULL){
            root = NULL;
            break;
        }
        if(temp->data==val){
            temp->data = delete_deepest_right(root);
            break;
        }

    }
    return root;
}

In the deletion function if the root node points to NULL value then we terminate the function and return back root itself otherwise we traverse through the entire tree to find the node which we need to delete. We terminate the while loop when we find the required node position.

Traversals in Binary Trees

Breadth First Traversal

Can be implemented using a queue

We print the value of the current node & add its left and right child to the queue.

We can keep repeating the process until the queue is empty.

Similar to the way we find the required node for deletion in the above code implementations.

Iterative function

Depth First Traversal

Inorder Traversal (Left-Root-Right)

Preorder Traversal (Root-Left-Right)

Postorder Traversal (Left-Right-Root)

Recursive approach