DAY 54 - Traversals in a Binary Tree

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

1. If(root == null)
2. return ;
3. vector 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.