Discover the power of linked lists in constructing binary trees. In this comprehensive guide, we'll walk you through the step-by-step process, whether you're a beginner or an experienced programmer. Unleash the potential of efficient data management with our tutorial on creating a binary tree using linked lists. We will be using queues in the process so do remember to add the queue header file with #include<queue> if you don't have your Queue class defined.

Node Class

First, we will be writing the node class this node class greatly resembles the node class of the Doubly Linked List. In the Doubly Linked list, we kept track of Head and Tail. In the Node Class of the Binary tree, we keep track of the Right and Left Child of the parent Node. The code for the node class is given below. We will be keeping the attributes public for this so it is easy to maneuver.

class Node {
public:
    int data;//data part
    Node* right;//For right child of node
    Node* left;//For Left child of Node
    Node(int data) {//parameterized constructor to initialize values
        this->data = data;//assigning data
        right = NULL;//intializing pointer with NULL
        left = NULL;//initializing pointer with NULL
    }
};

the code is very simple and easy to understand the parameterized constructor is being used to initialize the data at the time of Node creation.

Tree Class

In the tree class, we have one Node which we will call the root Node Which will tell us where our tree will start. Take a look at the code below and it will be explained module by module below.

class Tree {//tree class
public:
    Node* root;//node object
    Tree() {
        root = NULL;//assigning root to NULL
    }
    void add(int data)//Function to add data 
    {
        Node* N = new Node(data);//creating new node with the data
        queue <Node*> nodes;//creating a queue to hold node type data
        Node* temp;//creating a temp variable

        //IF root equals to Null it means Tree is Empty.

        if (root == NULL) {
            root = N;//assigning new node to tree.
            return;
        }
        else {    
            nodes.push(root);//we push the parent node to queue
            while (!nodes.empty()) {//until the queue is not empty
                temp = nodes.front();//we get the first node
                nodes.pop();//remove it from the queue
                if (temp->right != NULL && temp->left != NULL)//If the right and left of the node are not empty it means they are full
                {
                    //this means right and left node are filled which means it is a parent node
                    nodes.push(temp->left);//push the left node to queue
                    nodes.push(temp->right);//push right node to queue
                }
                else {
                    if (temp->left == NULL) //if left node empty we
                    {
                        temp->left = N;//set temp left as the node
                    }
                    else {
                        temp->right = N;//set temp's right as the node.
                    }
                    break;//break after assigning node
                }
            }
        }
    }
};

Add function

void add(int data)//Function to add data 
    {
        Node* N = new Node(data);//creating new node with the data
        queue <Node*> nodes;//creating a queue to hold node type data
        Node* temp;//creating a temp variable

        //IF root equals to Null it means Tree is Empty.

        if (root == NULL) {
            root = N;//assigning new node to tree.
            return;
        }
        else {    
            nodes.push(root);//we push the parent node to queue
            while (!nodes.empty()) {//until the queue is not empty
                temp = nodes.front();//we get the first nodeq
                nodes.pop();//remove it from the queue
                if (temp->right != NULL && temp->left != NULL)//If the right and left of the node are not empty it means they are full
                {
                    //this means right and left node are filled which means it is a parent node
                    nodes.push(temp->left);//push the left node to queue
                    nodes.push(temp->right);//push right node to queue
                }
                else {
                    if (temp->left == NULL) //if left node empty we
                    {
                        temp->left = N;//set temp left as the node
                    }
                    else {
                        temp->right = N;//set temp's right as the node.
                    }
                    break;//break after assigning node
                }
            }
        }
    }

The add function takes data to be added to the tree as a parameter.

1. After that, we create a queue usage that will be explained in the pseudo Code below.

2. After that, we create a temp node so we can use that and assign its right or left pointer a child.

3. After that, it checks if the root Node is NULL or not which means if the Root Node is empty or not. If the root Node is empty we just make the New Node The root Node.

4. If The root node is not empty and we have to add it as a child that is a little complex.

5. we push the root node to the queue. While the queue does not get empty we run the while loop. we pop the first node from the queue and assign it to the temp variable and pop it from the queue.

6. if the right and left of the popped Node are not empty that means that the node is a parent node and it has a further child so we append it to our queue.

7. Repeat steps 4,5,6 till we find a node that has an empty side or let us say free side.

8. After it is found we check which Side is empty if the right side is empty we assign the node to the right side. If the left side is empty we assign the node to the left side.

Display Function

The display function for this is written using recursion. you can see the function below.

void transversal(Node* tem) {
    if (tem->left != NULL)
        transversal(tem->left);
    cout << tem->data << " ";
    if (tem->right != NULL)
        transversal(tem->right);
}

The function takes a Dynamic node type pointer as a parameter. and it checks if the left side of the pointer is empty or not if it is not it calls the transversal function on that side and keeps calling it till it does not explore the whole left side. and then it starts printing the data after printing the right side same process is repeated for the left side and vice versa.

Next, We will be discussing different search algorithms like DFS(Depth First Search) and BFS(Breadth First Search) on trees and we will explore other types of trees as well.