What is a Binary tree?

A binary tree is tree data structure in which each node can have at most two child nodes referred to as the left and right child.

The two types of binary trees on which we are going to focus today are full and complete binary tree.

Full binary tree

A full binary tree is a type of binary tree in which each node except the leaf node has exactly two children.

Complete binary tree

A type of binary tree in which each level is completely filled except possibly for the last level which is filled from left to right.

In simple words, starting from left whenever any node has no child either left or right i.e. there is a break, any other node after it should not have any child at all.

---

Now we will implement a tree data structure using arrays in C++.

Working of each function is explained after the code.

// Necessary header files
#include <iostream>
#include <cmath>
using namespace std;

// class named BinaryTree
class BinaryTree
{
private:

    // total size of the array / binary tree
    int size;

    // to count the total number of nodes in binary tree
    int noOfElements;

    /* to check if a certain node is empty or filled. It is initialized 
    by -1 to show availability and whenever an element is inserted the 
    -1 at that particular index is changed to any other number showing 
    it is occupied */ 
    int *avail;

    // to store the nodes in format of array 
    int *data;

    /* Helper function of the displayPreOrder function to print the
    nodes of the tree according to preorder traversal */ 
    void displayPreOrder(int i)
    {
        if (i < size && avail[i] != -1)
        {
            cout << data[i] << " ";
            displayPreOrder((i + i) + 1);
            displayPreOrder((i + i) + 2);
        }
    }

    /* Helper function of the displayInOrder function to print the
    nodes of the tree according to inorder traversal */ 
    void displayInOrder(int i)
    {
        if (i < size && avail[i] != -1)
        {
            displayInOrder((i + i) + 1);
            cout << data[i] << " ";
            displayInOrder((i + i) + 2);
        }
    }

    /* Helper function of the displayPostOrder function to print the
    nodes of the tree according to postorder traversal */ 
    void displayPostOrder(int i)
    {
        if (i < size && avail[i] != -1)
        {
            displayPostOrder((i + i) + 1);
            displayPostOrder((i + i) + 2);
            cout << data[i] << " ";
        }
    }

    /* If the array gets filled this function can be called to increase
    the size of the original array */
    void resize()
    {
        int newSize = size + 15;
        int *newData = new int[newSize];
        int *newAvail = new int[newSize];
        for (int i = 0; i < size; i++)
        {
            newAvail[i] = avail[i];
            newData[i] = data[i];
        }
        for (int i = size; i < newSize; i++)
        {
            newAvail[i] = -1;
        }
        data = newData;
        avail = newAvail;
        size = newSize;
    }

public:

    /* Default constructor to initialize all the data members of class 
    BinaryTree */
    BinaryTree()
    {
        size = 10;
        noOfElements = 0;
        avail = new int[size];
        for (int i = 0; i < size; i++)
        {
            avail[i] = -1;
        }
        data = new int[size];
    } 

    // Constructor to initialize the data members
    BinaryTree(int size)
    {
        if (size < 10)
        {
            this->size = 10;
        }
        else
        {
            this->size = size;
        }
        data = new int[this->size];
        noOfElements = 0;
        avail = new int[this->size];
        for (int i = 0; i < size; i++)
        {
            avail[i] = -1;
        }
    } 

    /* Insert function to insert an element at the first non-filled 
    index of array */
    void insertElement(int element)
    {
        if (noOfElements == size)
        {
            resize();
        }
        data[noOfElements] = element;
        avail[noOfElements] = 5;
        noOfElements++;
    }

    /* This function inserts a left child of the element provided. If the
    element provided is not found or if its left child already exists it 
    returns false */
    bool insertLeftChild(int parent, int child)
    {
        int index = -1;
        for (int i = 0; i < noOfElements; i++)
        {
            if (data[i] == parent)
            {
                index = i;
                break;
            }
        }
        if (index == -1)
        {
            cout << "Element not found" << endl;
            return false;
        }
        else
        {
            int leftChild = 2 * index + 1;
            if (leftChild >= size)
            {
                resize();
            }

            if (avail[leftChild] != -1)
            {
                cout << "Left already exists" << endl;
                return false;
            }
            else
            {
                data[leftChild] = child;
                avail[leftChild] = 5;
                noOfElements++;
                return true;
            }
        }
    }

    /* This function inserts a right child of the element provided. If 
    the element provided is not found or if its right child already 
    exists it returns false */
    bool insertRightChild(int parent, int child)
    {
        int index = -1;
        for (int i = 0; i < noOfElements; i++)
        {
            if (data[i] == parent)
            {
                index = i;
                break;
            }
        }
        if (index == -1)
        {
            cout << "Parent not found" << endl;
            return false;
        }
        else
        {
            int rightChild = 2 * index + 2;
            if (rightChild >= size)
            {
                resize();
            }

            if (avail[rightChild] != -1)
            {
                cout << "Right already exists" << endl;
                return false;
            }
            else
            {
                data[rightChild] = child;
                avail[rightChild] = 5;
                noOfElements++;
                return true;
            }
        }
    }

    /* This function deletes the provided element by swapping the given
    element with the last element in the array and then deletes the last
    element. If the provided element is not found, it returns false */
    bool deleteElement(int element)
    {
        int index = -1;
        for (int i = 0; i < noOfElements; i++)
        {
            if (data[i] == element)
            {
                index = i;
                break;
            }
        }
        if (index == -1)
        {
            cout << "Element not found" << endl;
            return false;
        }
        else
        {
            int lastNodeIndex = size - 1;
            for (int i = size - 1; i >= 0; i--)
            {
                if (avail[i] != -1)
                {
                    lastNodeIndex = i;
                    break;
                }
            }
            data[index] = data[lastNodeIndex];
            avail[lastNodeIndex] = -1;
            noOfElements--;
            return true;
        }
    }

    /* This display function prints the nodes of each level in a new line
    and if a certain node is empty, it prints _ at its place */
    void display_Level()
    {
        int level = 0;
        int count = 0;
        int nodesInCurrentLevel = 1;

        for (int i = 0; i < size; i++)
        {
            if (avail[i] != -1)
            {
                cout << data[i] << " ";
            }
            else
            {
                cout << "_ ";
            }
            count++;

            if (count == nodesInCurrentLevel)
            {
                cout << endl;
                level++;
                nodesInCurrentLevel = pow(2, level); 
                count = 0;
            }
        }
        cout<<endl;
    }

    // displays the contents of the tree using pre-order traversal
    void display_PreOrder()
    {
        displayPreOrder(0);
        cout << endl;
    }

    // displays the contents of the tree using in-order traversal
    void display_InOrder()
    {
        displayInOrder(0);
        cout << endl;
    }

    // displays the contents of the tree using post-order traversal
    void display_PostOrder()
    {
        displayPostOrder(0);
        cout << endl;
    }

    // returns the total number of nodes in the tree
    int totalElements()
    {
        return noOfElements;
    }

    // deletes the allocated memory from the heap
    ~BinaryTree()
    {
        delete[] avail;
        delete[] data;
    }
};

---

Working of each function

1. insertElement function

   This function first checks if the array is full or not. If it is full, it then calls the resize function to increase the size of original array making space for the new element. It finds the first available space in the array and inserts that element there. It also increments the count of noOfElements by 1.

2. resize function

   This function creates two pointers to new arrays namely newData and newAvail and copies the elements of the original data and avail into them respectively. It finally assigns newData and newAvail to data and avail respectively as newData and newAvail have no scope beyond this function. Note that it copies the original avail to newAvail and then initializes the remaining newAvail with -1 to maintain the functioning of avail.

3. insertLeftChild function

   This function takes two arguments parent and child. First a variable named index is initialized with the value -1 and then a for loop is used to iterate through the whole array to find the parent element and its index is stored in index variable. If after the loop terminates and value of index is still -1 it means that element is not present in the tree and the function returns.

   If the parent element is found, then we find its left index so that we can insert the child element there. We do this by using the formula 2*index+1 which takes to the index which is supposed to be the left child of the parent element. If it is out of bounds, we resize the array and then we check if it's available by checking the value of avail at that index. If it is not -1 it means it is already occupied and we return false saying that left child of the given parent element already exists. Otherwise, we insert the child element at that index and increment the count of noOfElements and change its avail value to anything other than -1.

4. insertRightChild function

   This function takes two arguments parent and child. First a variable named index is initialized with the value -1 and then a for loop is used to iterate through the whole array to find the parent element and its index is stored in index variable. If after the loop terminates and value of index is still -1 it means that element is not present in the tree and the function returns.

   If the parent element is found, then we find its right index so that we can insert the child element there. We do this by using the formula 2*index+2 which takes to the index which is supposed to be the right child of the parent element. If it is out of bounds, we resize the array and then we check if it's available by checking the value of avail at that index. If it is not -1 it means it is already occupied and we return false saying that right child of the given parent element already exists. Otherwise, we insert the child element at that index and increment the count of noOfElements and change its avail value to anything other than -1.

5. deleteElement function

   This function only takes a single argument which is the element that the user wants to delete. First a variable named index is initialized with the value -1 and then a for loop is used to iterate through the whole array to find the desired element and its index is stored in index variable. If after the loop terminates and value of index is still -1 it means that element is not present in the tree and the function returns.

   If the element is found, it then proceeds to find the last element of the tree by using a for loop that starts from end and the first element it finds which has avail value other than -1 it stores it into a variable called lastNodeIndex. It then places the value of this lastNodeIndex in place of the element that needs to be deleted and changes the avail value of lastNodeIndex to -1 showing that this particular index is once again available for insertion. noOfElements is also decremented by 1.

6. display_Level function

   This function finds the number of nodes in each level by using the formula

   $$2^n$$

   where n is the level or height and stores them in variable called nodesInCurrentLevel. A variable named count is also initialized to 0 and whenever a value or _ is printed its value is incremented and when its value becomes equal to nodesInCurrentLevel it means a level is finished so a new line is printed, and value of count is again assigned zero value to maintain correct count of the nodes in new level. Nodes in the next level are found by using the same formula but the value of n is increased by 1.

7. display_PreOrder function

   It traverses the tree in pre order fashion and prints the value in that order. It does so by using the VLR principle which means

   Visit the current node.

   Go to the left subtree.

   Go to the right subtree.

8. display_InOrder function

   It traverses the tree in in order fashion and prints the value in that order. It does so by using the LVR principle which means

   Go to the left subtree.

   Visit the current node.

   Go to the right subtree.

9. display_PostOrder function

   It traverses the tree in post order fashion and prints the value in that order. It does so by using the LRV principle which means

   Go to the left subtree.

   Go to the right subtree.

   Visit the current node.

10. totalElements function

    Returns the total number of nodes in the tree.

---

I hope you found this detailed post on binary trees informative. If you have any questions or reviews comment them. I will answer to all of them.