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
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.
Contact Us