InOrder Traversal Code
LEFT SUBTREE → ROOT NODE → RIGHT SUBTREE
Binary Tree we'll use ↓
- In first step, the left subtree as a completely different one and apply inOrder separetely to it. But before you start with the left subtree, make sure to mark the presence of the root node and the right subtree as following ↓
- Now, you go through the left subtree, and further visit the left subtree of this new tree first.
- And then you proceed with the root of this new tree we considered.
- And after that, you visit the right subtree of this tree which has just a single element.
- With that being visited you move back to the original tree. And here, we visit the root node first and then the right subtree, and since it contains no left or right subtree further, we finish visiting our right subtree. There we mark the end of our InOrder traversal.
And our final order of inorder traversal is : 5 → 1 → 2 → 4 → 6
Creating inOrder function
- Create a void function inOrder and pass the pointer to the root node of the tree you want to traverse as the only parameter.
- Inside the function, check it the pointer is not NULL
- If not NULLcall the same function recursively on the left subtree using the left element of the root struct.
- After we finish visiting the left subtree, we print the data element of the root node indicating it as visited.
- Having visited both the left subtree and the root, we now move to the right subtree and call it recursively. This completes our flow. and we are done visiting all the nodes.
void inOrder(struct node* root){
if(root!=NULL){
inOrder(root->left);
printf("%d ", root->data);
inOrder(root->right);
}
}
#include
#include
struct node{
int data;
struct node* left;
struct node* right;
};
struct node* createNode(int data){
struct node *n; // creating a node pointer
n = (struct node *) malloc(sizeof(struct node)); // Allocating memory in the heap
n->data = data; // Setting the data
n->left = NULL; // Setting the left and right children to NULL
n->right = NULL; // Setting the left and right children to NULL
return n; // Finally returning the created node
}
void preOrder(struct node* root){
if(root!=NULL){
printf("%d ", root->data);
preOrder(root->left);
preOrder(root->right);
}
}
void postOrder(struct node* root){
if(root!=NULL){
postOrder(root->left);
postOrder(root->right);
printf("%d ", root->data);
}
}
void inOrder(struct node* root){
if(root!=NULL){
inOrder(root->left);
printf("%d ", root->data);
inOrder(root->right);
}
}
int main(){
// Constructing the root node - Using Function (Recommended)
struct node *p = createNode(4);
struct node *p1 = createNode(1);
struct node *p2 = createNode(6);
struct node *p3 = createNode(5);
struct node *p4 = createNode(2);
// Finally The tree looks like this:
// 4
// / \
// 1 6
// / \
// 5 2
// Linking the root node with left and right children
p->left = p1;
p->right = p2;
p1->left = p3;
p1->right = p4;
// preOrder(p);
// printf("\n");
// postOrder(p);
// printf("\n");
inOrder(p);
return 0;
}