Preorder Tree Traversal of Binary Tree in C
A binary tree is a hierarchical data structure composed of nodes where each node has at most two children. It can referred to as the left child and the right child. Due to having a non-linear structure, a binary tree can be traversed in multiple ways. One such way is preorder traversal which is a Depth First (DFS) Traversal technique.
In this article, we will learn how to implement preorder binary tree traversal in C and analyze its space and time complexity.
Preorder Traversal of Binary Tree in C
Preorder traversal is a DFS tree traversal technique that first visits the current node, traverses the left sub-tree as far as it can and then traverses the right sub-tree.
Pre-order Traversal
- Visit the root node.
- Then, recursively traverse the left subtree.
- Finally, recursively traverse the right subtree.
Consider the following example,
For preorder traversal of the above tree:
- Start at the root node (1).
- Visit the root node then print it.
- Traverse the left subtree of the root (2).
- Visit the root of the left subtree (2) and print it.
- Traverse the left subtree of the node 2(4) and visit 4 and print it.
- Backtrack to the node 2 and traverse its right subtree (5) and visit and print it.
- Backtrack to the root node (1).
- Traverse the right subtree of root (3).
- Visit the root of the right subtree (3) and print it.
The pre-order traversal of the binary tree: 1, 2, 4, 5, 3
Algorithm for Pre-Order Binary Tree Traversal
Following is the algorithm of the pre-order binary tree traversal:
preOrder(root) {
If root is NULL
return
visit root->data
preOrder(root->leftChild)
preOrder(root->rightChild)
return
}
C++ Program to Implement Preorder Traversal of the Binary Tree
// C Program to illustrate how to implement the preorder
// binary tree traversal
#include <stdio.h>
#include <stdlib.h>
// creating tree node
struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
};
// utility function to create a node with given value
struct TreeNode* createNode(int val)
{
struct TreeNode* newNode
= (struct TreeNode*)malloc(sizeof(struct TreeNode));
newNode->val = val;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// preorder traversal
void preorderTraversal(struct TreeNode* root)
{
// if the current node is empty
if (root == NULL)
return;
// visiting node
printf("%d ", root->val);
// going to left subtree
preorderTraversal(root->left);
// going to right subtree
preorderTraversal(root->right);
}
// drive code
int main()
{
// creating example tree
struct TreeNode* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
printf("Preorder Traversal: ");
preorderTraversal(root);
return 0;
}
Output
Preorder Traversal: 1 2 4 5 3
Time Complexity
From the above example, we can see that we are visiting each node in the tree three times so,
The time complexity of the Preorder Binary Tree Traversal is O(n)
Auxiliary Space Complexity
The space complexity of the preorder traversal will depend upon the structure of the tree.
If the tree is skewed, then the auxiliary space complexity will be O(n). While for the balanced tree, it will be O(logN).
Refer to this article for more detailed time and space complexity analysis.
Applications
Following are some major application of the preorder binary tree traversal:
- It can applies on the expression evaluation.
- It can applies on the Complier construction.
- It can applies on the Syntax tree generation.
- It can applies on Mathematical expression parsing.