C Program to Implement Inorder Binary Tree Traversal
// C program to show how to implement the binary tree
// traversal
#include <stdio.h>
#include <stdlib.h>
// node of the tree
struct Node {
int data;
struct Node* left;
struct Node* right;
};
// utility function to create a node
struct Node* createNode(int data)
{
struct Node* newNode
= (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// Function to perform inorder traversal
void inorderTraversal(struct Node* root)
{
// cheking if the current node is NULL
if (!root)
return;
// traversing left subtree
inorderTraversal(root->left);
// traversing current node
printf("%d ", root->data);
// traversing right subtree
inorderTraversal(root->right);
}
int main()
{
// Example tree creation
struct Node* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
printf("Inorder Traversal: ");
inorderTraversal(root);
return 0;
}
Output
Inorder Traversal: 4 2 5 1 3
Time Complexity
The time complexity of the inorder traversal is O(n) just like all the other DFS tree traversals.
Space Complexity
Due to recursion stack dependency on the structure of the tree, the auxiliary space complexity of the inorder binary tree traversal will also depend on the structure of the tree:
- For skew/degenerate trees, the space complexity will be O(n).
- For balanced tree, the space complexity will be O(log n)
Refer to this article for more detailed time and space complexity analysis.
Inorder Tree Traversal in Binary Tree in C
A binary Tree is a hierarchical data structure in which each node has at most two children and it can referred to as the left child and right child. Due to being a non-linear data structure, different traversal techniques are possible for it.
Inorder tree traversal is one of the techniques used to visit each node of the binary tree. In this article, we will learn how to implement the in-order traversal technique for binary tree traversal in C. We will also discuss its time and space complexities.