DAY 54 - Traversals in a Binary Tree
Tags: algorithms, css, datastructures, tutorial
Published: 2023-07-27 17:06:33

Welcome to DAY 54. Today we will diverge into the Data Structure Trees.
[Content Credits](https://www.codingninjas.com/studio/guided-paths/data-structures-algorithms/content/118521/offering/1380974)
## Theory:
We know that linked list is one node pointing to another and then that node pointing to another node making an interconnected list.
`Ex: 1->2->3->4`

A tree is a data structure similar to linked lists but instead of each node pointing to the next node in a linear manner, each node can point to a number of nodes making it a non linear structure.

To get ahead we must know some terminologies used in trees:

**_Root Node:_** The root node of tree is the node with no parents. There is only one root node in an entire tree.
**_Parent:_** The node of tree which points to one or more node is a parent of that node.
_**Edge:**_ A link between parent and child node.
_**Leaf:**_ Node with no children is a leaf node.
_**Siblings:**_ Children with same parents are siblings to each other.

---

![Fig 1.1](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/cnc6mbwft86krybtybqt.png)



**_A binary tree is a tree with at most 2 child nodes.(Fig 1.1)_**


## Traversals in a binary Tree:
_Here:_

> - L -> Left
> - R -> Right
> - N -> Node


### PreOrder Traversal(NLR):
- Visit the root node.
- Traverse the left subtree
- Traverse the right subtree

1. If(root == null) 
2. return ;
3. vector<int> preOrder.push_back(root)
4. preOrderTraversal(root->left)
5. preOrderTraversal(root->right)

**Output:** `1 2 4 5 3 6 7`

---

### InOrder Traversal(LNR):
- Traverse the left subtree
- Visit the root node.
- Traverse the right subtree

1. If(root == null) 
2. return ;
3. inOrderTraversal(root->left)
4. inOrder.push_back(root)
5. inOrderTraversal(root->right)

**Output:** `4 2 5 1 6 3 7`

---

### PostOrder Traversal(LRN):


- Traverse the left subtree
- Traverse the right subtree
- Visit the root node.

1. If(root == null) 
2. return ;
3. postOrderTraversal(root->left)
4. postOrderTraversal(root->right)
5. postOrder.push_back(root)

**Output:** `4 5 2 6 7 3 1`

## Code:

```
#include <bits/stdc++.h>
using namespace std;

struct node {
  int data;
  struct node * left, * right;
};

void allTraversal(node * root, vector < int > & pre, vector < int > & in , vector < int > & post)
{
    stack<pair<node*, int>> st;
    st.push({root,1});

    if(root == NULL)

    {
        return ;
    }
    //pre order
    while(!st.empty())
    {
        auto it = st.top();
        st.pop();

        if(it.second == 1)
        {
            pre.push_back(it.first->data);
            it.second ++;
            st.push(it);

            if(it.first->left != NULL)
            {
                st.push({it.first->left,1});
            }

        }

        //in order


       else  if(it.second == 2)
        {
            in.push_back(it.first->data);
            it.second++;
            st.push(it);

            if(it.first->right != NULL)
            {
                st.push({it.first->right,1});
            }
        }
        //post
         else{
            post.push_back(it.first->data);
         }

    }
}
struct node * newNode(int data) {
  struct node * node = (struct node * ) malloc(sizeof(struct node));
  node -> data = data;
  node -> left = NULL;
  node -> right = NULL;

  return (node);
}

int main() {

  struct node * root = newNode(1);
  root -> left = newNode(2);
  root -> left -> left = newNode(4);
  root -> left -> right = newNode(5);
  root -> right = newNode(3);
  root -> right -> left = newNode(6);
  root -> right -> right = newNode(7);

  vector < int > pre, in , post;
  allTraversal(root, pre, in , post);

  cout << "The preorder Traversal is : ";
  for (auto nodeVal: pre) {
    cout << nodeVal << " ";
  }
  cout << endl;
  cout << "The inorder Traversal is : ";
  for (auto nodeVal: in ) {
    cout << nodeVal << " ";
  }
  cout << endl;
  cout << "The postorder Traversal is : ";
  for (auto nodeVal: post) {
    cout << nodeVal << " ";
  }
  cout << endl;

  return 0;
}
```

Thanks for reading. We will be covering BFS and DFS approach in the next article and doing some basic questions.