Welcome to DAY 54. Today we will diverge into the Data Structure Trees.
Content Credits

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.

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

If(root == null)
return ;
vector preOrder.push_back(root)
preOrderTraversal(root->left)
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

If(root == null)
return ;
inOrderTraversal(root->left)
inOrder.push_back(root)
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.

If(root == null)
return ;
postOrderTraversal(root->left)
postOrderTraversal(root->right)
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.

DAY 54 - Traversals in a Binary Tree