---

title: 'Trees Introduction' author: 'zaheen' topic : 'trees' subtopic: ['tree-into'] description: 'An intoduction to trees, ints implementaion and traversal'

---

title: 'Trees Introduction' author: 'zaheen' topic : 'trees' subtopic: ['tree-into'] description: 'An intoduction to trees, ints implementaion and traversal'

Trees Implementation and Traversal

The representation of a tree is as shown below. it has different nodes and they are connected together to form a tree.

the above picture is a binary tree where each node has less than or equal to 2 child. similarly we have n-array tree where a node has n child.

Here is a list of some common terminologies used in trees:

• node: A node is a single element in tree which contains data and the pointer to next nodes
• child: A child is the direct lower nodes corresponding to a node.
• ancestors: All the nodes above a node is called ancestors.
• parent: Parent is the direct above node of a given node.
• leaf node: is the node which dos not have any child .

Creation of tree

we can create a tree from two methods -

1. Basic recursion
2. Level order traversal

Basic recursion :

• here we make use of recursion to build the tree.
• It begins by defining a class "Node" with properties "data", "left", and "right".
• The "Node" class has a constructor that assigns data to the node and initializes its left and right child nodes as NULL.
• The function "createTree()" uses recursion to create the tree:
  • It prompts the user to input data.
  • The entered data is assigned as the new node's data.
  • The function then asks for the left and right child node of the current node and recursively creates those nodes.

#include<iostream>
#include<queue>

using namespace std;

class Node {
    public:
        int data;
        Node* left;
        Node* right;

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

Node* createTree() {
    cout << "Enter the data" << endl;
    int data;
    cin >> data;
    if(data == -1) {
        return NULL;
    }
    Node* root = new Node(data);
    cout << "Enter the data left of " << data << endl;
    root->left = createTree();
    cout << "Enter the data right of " << data << endl;
    root->right = createTree();
    return root;
}

int main() {
    Node* root = createTree();
    return 0;
}

Level order traversal :

• A new Node is created with the entered data as root.
• A queue is created and the root Node is added to it.
• A while loop is initiated that continues as long as the queue is not empty.
• The Node at the front of the queue is temporarily held in a variable and then removed from the queue.
• The user is prompted to enter the data for the left child of the current Node.
• If the entered data is not -1, a new Node is created with the entered data and added as the left child of the current Node. This new Node is also added to the queue.
• The user is then prompted to enter the data for the right child of the current Node.
• If the entered data is not -1, a new Node is created with the entered data and added as the right child of the current Node. This new Node is also added to the queue.
• This process repeats until all Nodes have been created and added to the tree in a level order traversal manner.

void levelOrderTraversal()
{
    cout<<"enter the root data"<<endl;
    int data;
    cin>>data;

    Node* root = new Node(data);
    queue<Node*> q;
    q.push(root);

    while(!q.empty()){
        Node* temp = q.front();
        q.pop();
        cout<<"Enter the left data of "<<temp->data<<endl;
        int leftd ;
        cin>>leftd;

        if(leftd!=-1){
            temp->left=new Node(leftd);
            q.push(temp->left);
        }

        cout<<"Enter the right data of "<<temp->data<<endl;
        int rightd ;
        cin>>rightd;

        if(rightd!=-1){
            temp->right=new Node(rightd);
            q.push(temp->right);
        }
    }
  
}

Traversal in a tree

We have looked into various ways of creating a tree. now we will jump into the traversal part of trees. we have mainly 3 ways of traversing a tree, namely -

• Level order traversal - here we will traverse the tree level by level.
• In order traversal - here we will traverse the all left nodes first then print the nodes and then traverse the right node
• Post order traversal - here we will traverse the all left and right nodes respectively, then print the nodes
• Pre order traversal - here we will print the node and then traverse the left and right nodes respectively

Now we will see the codes of the above traversals.

In order traversal

void inorderTraversal(Node *root)
{
    queue<Node *> q;
    q.push(root);
    q.push(NULL);

    while (!q.empty())
    {
        Node *temp = q.front();
        q.pop();

        if (temp == NULL)
        {
            cout << endl;
            if (!q.empty())
            {
                q.push(NULL);
            }
        }
        else
        {
            cout << temp->data << " ";

            if (temp->left)
            {
                q.push(temp->left);
            }

            if (temp->right)
            {
                q.push(temp->right);
            }
        }
    }
}

Pre order traversal

void preOrderTraversal(Node *root)
{
    if (root == NULL)
    {
        return;
    }

    cout << root->data;
    preOrderTraversal(root->left);
    preOrderTraversal(root->right);
}

Post order traversal

void postOrderTraversal(Node *root)
{
    if (root == NULL)
    {
        return;
    }

    postOrderTraversal(root->left);
    postOrderTraversal(root->right);

    cout << root->data;
}