.png)
[Follow here] for daily coding insights
DSA Series Chapter 13 - Binary Tree traversal, BFS, DFT/DFS, Preorder Traversal In Binary Tree
In Binary Tree traversal, the terms BFS and DFS (often written as DFT – Depth First Traversal) are high-level traversal categories, not individual algorithms.
1. What is BFS in Binary Tree Traversal?
BFS – Breadth First Search (Traversal)
Meaning:
BFS visits nodes level by level, from top to bottom and left to right.
Key Characteristics
Traverses breadth-wise
Uses a Queue
Also called Level Order Traversal
Traverses breadth-wise
Uses a Queue
Also called Level Order Traversal
Order Pattern
Level 0 → Level 1 → Level 2 → ...
Level 0 → Level 1 → Level 2 → ...
Example Output
For a tree:
1
/ \
2 3
/ \
4 5
BFS Output:
1 2 3 4 5
Exam Note
BFS in a binary tree is implemented using a queue.
BFS in a binary tree is implemented using a queue.
2. What is DFS / DFT in Binary Tree Traversal?
DFS / DFT – Depth First Traversal
Meaning:
DFS goes deep into a subtree before visiting siblings.
Key Characteristics
Traverses depth-wise
Uses recursion or stack
DFS is a category, not a single traversal
Traverses depth-wise
Uses recursion or stack
DFS is a category, not a single traversal
3. Types of DFS (Very Important)
DFS has three standard types in a binary tree:
1. Preorder Traversal
Root → Left → Right
Root → Left → Right
2. Inorder Traversal
Left → Root → Right
Left → Root → Right
3. Postorder Traversal
Left → Right → Root
Left → Right → Root
Exam Note
DFS in binary trees is performed using preorder, inorder, or postorder traversal.
DFS in binary trees is performed using preorder, inorder, or postorder traversal.
5. Are There Any Other Traversal Types?
Standard Traversals (Syllabus Level)
✔ BFS
✔ DFS (Preorder, Inorder, Postorder)
Advanced / Special Traversals (Optional Knowledge)
These exist but are not mandatory for basic DSA:
Morris Traversal
Inorder traversal without stack or recursion
Zig-Zag Traversal
Alternate left-right order per level
Boundary Traversal
Vertical Order Traversal
Diagonal Traversal
These are variations built on BFS or DFS, not new fundamental categories.
PREORDER TRAVERSAL (BINARY TREE)
Objective of this Post
This post explains Preorder Traversal of a Binary Tree in complete detail, using:
A single clear diagram
Step-by-step traversal logic
Standalone C program
Dry run, complexity, and exam notes
This is an individual post, meant to be taught and revised independently.
1. What is Preorder Traversal?
Definition (Exam-ready)
Preorder traversal is a depth-first traversal technique in which the root node is visited first, followed by the left subtree and then the right subtree.
Traversal Order
Root → Left → Right
2. Binary Tree Diagram Used
1
/ \
2 3
/ \
4 5
This same tree will be used for logic explanation, dry run, and program output.
3. Step-by-Step Preorder Traversal on Diagram
Traversal rule: Root → Left → Right
Visit root → 1
Go to left subtree of 1
Visit 2
Go to left subtree of 2
Visit 4
Left and right of 4 are NULL → return
Visit right child of 2 → 5
Left and right of 5 are NULL → return
Go to right subtree of root 1
Visit 3
Final Preorder Output
1 2 4 5 3
4. Algorithm (Recursive – Plain English)
If the current node is NULL, return
Visit the current node
Traverse the left subtree recursively
Traverse the right subtree recursively
5. Recursive Algorithm (Pseudo Code)
PREORDER(node)
{
if(node != NULL)
{
visit(node)
PREORDER(node->left)
PREORDER(node->right)
}
}
6. C Program – Preorder Traversal (Recursive)
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *left;
struct Node *right;
};
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;
}
void preorder(struct Node* root)
{
if (root != NULL)
{
printf("%d ", root->data);
preorder(root->left);
preorder(root->right);
}
}
int main()
{
struct Node* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
printf("Preorder Traversal: ");
preorder(root);
return 0;
}
7. Dry Run of Recursive Calls
preorder(1)
print 1
preorder(2)
print 2
preorder(4)
print 4
preorder(NULL)
preorder(5)
print 5
preorder(3)
print 3
8. Time and Space Complexity
Time Complexity
O(n) where n is number of nodes
Each node is visited exactly once
Space Complexity
O(h) due to recursion stack
h = height of tree
Worst case (skewed tree): O(n)
9. Important Applications of Preorder Traversal
Creating a copy of a tree
Prefix expression generation
Tree serialization
Structure reconstruction
10. Common Exam & Interview Mistakes
Printing root after left subtree (that becomes inorder)
Forgetting base condition (root != NULL)
Assuming preorder always gives sorted output
11. Practice Questions
Write preorder traversal for the following tree (drawn in exam).
Predict preorder output for a skewed binary tree.
Convert recursive preorder traversal into iterative logic.
What happens to recursion stack in worst case?
12. Learning Outcome
After this post, a student can:
Explain preorder traversal confidently
Dry-run preorder traversal on any diagram
Write recursive preorder traversal in C
Analyze time and space complexity
ALSO CHECK
ALSO CHECK
Comments
Post a Comment