What is Tree Traversal? (Tree Traversal क्या है?)
Tree Traversal एक process है, जिसमें Tree Data Structure के सभी nodes को एक specific order में visit किया जाता है। क्योंकि Tree में data linear order में नहीं, hierarchical form में होता है, इसलिए nodes को directly sequence में access नहीं किया जा सकता।
इसी problem को solve करने के लिए Tree Traversal techniques का use किया जाता है।
Why Do We Need Tree Traversal?
(Tree Traversal की आवश्यकता क्यों है?)
Tree Data Structure में data linear form (जैसे Array या Linked List) में store नहीं होता, यह hierarchical structure में arrange रहता है। इस structure में एक Root node, उसके नीचे child nodes और सबसे नीचे leaf nodes होते हैं।
- Tree के हर node का data read, search, calculate या manage करना हो, तो Tree Traversal का use किया जाता है।
मुख्य कारण :
- All Nodes को Access करने के लिए
- Tree में nodes अलग-अलग levels पर होते हैं।
- Traversal के बिना हम सभी nodes तक नहीं पहुँच सकते।
- Example : Computer File System→ Root Folder → Sub Folder → Files
- Data Processing के लिए
- Tree का use calculation और processing में भी होता है।
- Example : Expression Tree में calculation
- Searching के लिए
- Tree में किसी value या record को search करने के लिए traversal जरूरी है।
- Example : IRCTC route structure
- Expression Evaluation के लिए
- Traversal से different expressions मिलती हैं :
- Inorder → Infix
- Preorder → Prefix
- Postorder → Postfix
- Sorted Data पाने के लिए
- Binary Search Tree (BST) में Inorder Traversal sorted output देता है।
- Example : Student Roll Numbers (ascending order)
Tree Example (उदाहरण)
A
/ \
B C
/ \
D E
- A = Root node
- B, C = Child nodes
- D, E = Leaf nodes
Types of Traversal (प्रकार)
Traversal mainly दो types का होता है :
- Depth First Traversal (DFS)
- Breadth First Traversal (BFS)
1. Depth First Traversal (DFS)
Depth First Traversal (DFS) Tree Traversal की एक important technique है, जिसमें Tree को गहराई (depth) में explore किया जाता है। इस traversal में हम root node से start करके एक branch को पूरा end तक traverse करते हैं, और फिर backtrack करके दूसरी branch पर जाते हैं।
Types of Depth First Traversal – DFS के तीन main types होते हैं :
- Preorder Traversal
- Inorder Traversal
- Postorder Traversal
1. Preorder Traversal (Root → Left → Right)
Preorder Traversal एक प्रकार का Depth First Traversal (DFS) है, जिसमें Tree के nodes को इस क्रम (order) में visit किया जाता है :
- Node → Left Subtree → Right Subtree
Algorithm
Preorder Traversal Algorithm (Steps)
- Visit the root node
- Traverse the left subtree using preorder
- Traverse the right subtree using preorder
Algorithm (Recursive Form)
Preorder(node):
1. If node == NULL
return
2. Visit(node)
3. Preorder(node.left)
4. Preorder(node.right)
Example
A
/ \
B C
/ \
D E
Step – by – Step Preorder Traversal
Step 1: Start from Root
- Visit A
- Output : A
Step 2: Move to Left Subtree of A
- Visit B
- Output : A, B
Step 3: Move to Left Subtree of B
- Visit D
- Output : A, B, D
Step 4: D has no children
Backtrack to parent B
Step 5: Move to Right Subtree of B
- Visit E
- Output : A, B, D, E
Step 6: B’s both subtrees are completed
Backtrack to A
Step 7: Move to Right Subtree of A
- Visit C
- Output : A, B, D, E, C
Final Preorder Traversal Output
- A → B → D → E → C
2. Inorder Traversal (Left → Root → Right)
Inorder Traversal एक प्रकार का Depth First Traversal (DFS) है, जिसमें Tree के nodes को इस क्रम में visit किया जाता है :
- Left Subtree → Root Node → Right Subtree
Algorithm
Inorder Traversal Algorithm (Steps)
- Traverse the left subtree
- Visit the root node
- Traverse the right subtree
Recursive Algorithm
Inorder(node):
1. If node == NULL
return
2. Inorder(node.left)
3. Visit(node)
4. Inorder(node.right)
Example
A
/ \
B C
/ \
D E
Step – by – Step Inorder Traversal
Step 1: Start from Root A
Go to left subtree → B
Step 2: From B, go to its left subtree → D
- Visit D
- Output : D
Step 3: Backtrack to B
- Visit B
- Output : D, B
Step 4: Go to right subtree of B → E
- Visit E
- Output : D, B, E
Step 5: Backtrack to Root A
- Visit A
- Output : D, B, E, A
Step 6: Go to right subtree of A → C
Visit C
Final Inorder Traversal Output
D → B → E → A → C
3. Postorder Traversal (Left → Right → Root)
Postorder Traversal एक प्रकार का Depth First Traversal (DFS) है, जिसमें Tree के nodes को इस क्रम (order) में visit किया जाता है :
- Left Subtree → Right Subtree → Root Node
Algorithm
Postorder Traversal Algorithm (Steps)
- Traverse the left subtree
- Traverse the right subtree
- Visit the root node
Recursive Algorithm
Postorder(node):
1. If node == NULL
return
2. Postorder(node.left)
3. Postorder(node.right)
4. Visit(node)
Example
A
/ \
B C
/ \
D E
Step – by – Step Postorder Traversal
Step 1: Start from Root A
Go to left subtree → B
Step 2: From B, go to its left subtree → D
- Visit D
- Output : D
Step 3: Backtrack to B
- Go to right subtree → E
- Visit E
- Output : D, E
Step 4: Now both children of B are processed
- Visit B
- Output : D, E, B
Step 5: Backtrack to Root A
- Go to right subtree → C
- Visit C
- Output : D, E, B, C
Step 6: Now both subtrees of A are processed
Visit A
Final Postorder Traversal Output
D → E → B → C → A
2. Breadth First Traversal (BFS)
Breadth First Traversal (BFS), जिसे Level Order Traversal भी कहा जाता है, एक Tree traversal technique है, जिसमें nodes को level by level और left-to-right order में visit किया जाता है।
Visual Representation :
A ← Level 0
/ \
B C ← Level 1
/ \
D E ← Level 2
Algorithm
- Create an empty queue
- Insert (enqueue) root node into the queue
- While queue is not empty :
- Remove (dequeue) node from the front
- Visit the node
- Enqueue its left child (if exists)
- Enqueue its right child (if exists)
Pseudo-Code
BFS(root) :
- Create an empty Queue Q
- Enqueue(root)
- While Q is not empty :
- node = Dequeue(Q)
- Visit(node)
- If node.left exists, Enqueue(node.left)
- If node.right exists, Enqueue(node.right)
Example
A
/ \
B C
/ \
D E
| Step | Queue | Node Visited | Output |
|---|---|---|---|
| 1 | A | A | A |
| 2 | B, C | B | A, B |
| 3 | C, D, E | C | A, B, C |
| 4 | D, E | D | A, B, C, D |
| 5 | E | E | A, B, C, D, E |
| 6 | Empty | Stop | Final Output : A, B, C, D, E |
Applications of Tree Traversal (अनुप्रयोग)
- Database Query Processing : SQL Queries execute करने में tree traversal use होता है।
- Artificial Intelligence (AI) : AI games जैसे Chess, Tic-Tac-Toe में Minimax algorithm DFS (Depth-First Search) traversal use करता है।
- File Systems : Linux / Windows filesystem hierarchy को explore करने में traversal का use होता है।
- Compilers : Expression Trees को evaluate करने के लिए Preorder/Postorder Traversal use होता है।
- Networking : Routing tables और network packet management में tree structures traversal use होते हैं।
- E-Commerce : Flipkart / Amazon जैसी sites में category → subcategory → product hierarchy traverse करने के लिए traversal use होता है।
Advantages of Tree Search and Traversal Techniques (लाभ)
- Efficient Data Access : Tree traversal techniques के कारण हम hierarchical data को efficiently access कर सकते हैं।
- Systematic Data Processing : Traversal methods (Preorder, Inorder, Postorder, BFS) nodes को systematically visit करते हैं, जिससे कोई node miss नहीं होता।
- Supports Hierarchical Representation : Tree natural hierarchical structure represent करता है, और traversal इसे top-down या bottom-up explore करने में मदद करता है।
- Applications in AI and Computer Systems : DFS (Preorder/Postorder/Inorder) और BFS का उपयोग AI search algorithms, pathfinding, और compiler syntax trees में होता है।
- Memory Efficient (Recursive DFS) : Recursive DFS methods call stack का उपयोग करती हैं, जिससे extra data structure की आवश्यकता कम होती है।
- Versatile : सभी types of trees में (Binary Tree, N-ary Tree, AVL Tree, B-Tree) traversal techniques काम करती हैं।
Disadvantages of Tree Search and Traversal Techniques(हानियाँ)
- Complex Implementation for Non-Recursive Methods : Non-recursive traversal (using stack or queue) कुछ cases में complex और error-prone होता है।
- Memory Usage in Deep Trees : Recursive DFS में stack overflow हो सकता है।
- Time Complexity for Unbalanced Trees : Unbalanced tree में worst-case traversal time O(n) हो जाता है, जिससे performance degrade हो सकती है।
- Limited Direct Access : direct access by index possible नहीं है। Traversal हमेशा systematic होना चाहिए।
- BFS Memory Requirement: Level-order traversal (BFS) में queue use होती है, जो बहुत बड़े tree में high memory consumption कर सकती है।
- Traversal Does Not Solve Problem Alone : Traversal केवल nodes visit करता है, problem-solving या data manipulation के लिए additional logic जरूरी है।
