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.
Top comments (0)