Tree Traversal in Data Structure
Introduction to Tree Traversal
Tree traversal in Data Structure deals with hierarchical data structures like trees. Trees are widely used to represent hierarchical relationships, such as file systems, organization structures, and the hierarchical structure of data in databases. Traversal refers to the process of visiting and examining all the nodes in a tree in a specific order.
Let’s jump into the article to know more about Tree Traversal in Data Structure and also you will get to know about four most important traversal : DFS, BFS, Boundary Traversal and Diagonal Traversal.
Tree Traversal in Data Structure
Tree traversal refers to the process of systematically visiting and examining each node (or element) within a tree structure in a specific order. This traversal allows you to access, process, or manipulate the data stored in the tree.
Tree Traversal in Data Structure Examples
Tree Traversal Algorithm in Data Structure
A tree data structure can undergo traversal using the following methods:
- Depth-First Traversal (DFS)
- Breadth-First Traversal (BFS)
- Boundary Traversal
- Diagonal Traversal
Depth-First Traversal (DFS)
Depth-first traversal is a technique that explores as far as possible along a branch of the tree before backtracking.
It can be implemented using three main approaches:
- Preorder traversal
- Inorder traversal
- Postorder traversal
1. Preorder Traversal
Preorder traversal visits the root node first, followed by the left subtree and then the right subtree. It is often used for tasks such as copying a tree, evaluating expressions, or creating a prefix expression from a binary expression tree.
Algorithm:
Procedure of PreorderTraversal in a tree :
1. Visit the root node.
2. Traverse the left subtree by recursively calling PreorderTraversal(left->subtree).
3. Traverse the right subtree by recursively calling PreorderTraversal(right->subtree).
Code :
class TreeNode:
def __init__(self, value):
self.val = value
self.left = None
self.right = None
def preorder_traversal(node):
if node is not None:
# Visit the current node
print(node.val)
# Traverse the left subtree
preorder_traversal(node.left)
# Traverse the right subtree
preorder_traversal(node.right)
# Create a sample binary tree
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
# Perform preorder traversal
print("Preorder traversal:")
preorder_traversal(root)
Output :
Preorder traversal: 1 2 4 5 3
Explanation :
- The code performs a preorder traversal of a binary tree. It defines a “TreeNode“ class to represent nodes, and a “preorder_traversal“ function.
- Starting at the root node, it prints each node’s value, then recursively traverses the left subtree and the right subtree.
- This order ensures nodes are visited in the sequence: root, left subtree, right subtree, printing the values in that order.
Complexity Analysis of Preorder Traversal
2. Inorder Traversal
Inorder traversal visits the left subtree first, followed by the root node, and then the right subtree. It is commonly used to visit nodes in sorted order for binary search trees (BSTs). In the case of a BST, an inorder traversal will visit the nodes in ascending order.
Algorithm:
Procedure for InorderTraversal in a tree :
1. Traverse the left subtree by recursively calling InorderTraversal(left->subtree).
2. Visit the current root node.
3. Traverse the right subtree by recursively calling InorderTraversal(right->subtree).
Code :
class TreeNode:
def __init__(self, value):
self.val = value
self.left = None
self.right = None
def inorder_traversal(node):
if node is not None:
# Traverse the left subtree
inorder_traversal(node.left)
# Visit the current node
print(node.val, end=" ")
# Traverse the right subtree
inorder_traversal(node.right)
#Creating a simple Binary Tree
root = TreeNode(15)
root.left = TreeNode(10)
root.right = TreeNode(20)
root.left.left = TreeNode(5)
root.left.right = TreeNode(12)
root.right.left = TreeNode(17)
root.right.right = TreeNode(25)
# Perform inorder traversal on the tree
print("Inorder traversal (Example):")
inorder_traversal(root)
Output :
Inorder traversal (Example): 5 10 12 15 17 20 25
Explanation :
- The Inorder Traversal code visits nodes in a binary tree in ascending order.
- It starts from the leftmost node, goes up to the root, and then moves to the right subtree.
- It recursively follows this pattern, ensuring nodes are processed in ascending order, making it useful for tasks like printing a binary search tree in sorted order.
Complexity Analysis of Inorder Traversal
3. Postorder Traversal
Postorder traversal visits the left subtree, followed by the right subtree, and then the root node. This traversal method is useful for tasks like deleting a tree, calculating the height of a tree, or evaluating postfix expressions from a binary expression tree.
Algorithm:
Procedure for PostorderTraversal in a tree :
1. Traverse the left subtree by recursively calling PostorderTraversal(left->subtree).
2. Traverse the right subtree by recursively calling PostorderTraversal(right->subtree).
3. Visit the current root node.
Code :
class TreeNode:
def __init__(self, value):
self.val = value
self.left = None
self.right = None
def postorder_traversal(node):
if node is not None:
# Traverse the left subtree
postorder_traversal(node.left)
# Traverse the right subtree
postorder_traversal(node.right)
# Visit the current node
print(node.val, end=" ")
# Create a sample binary tree
root = TreeNode(8)
root.left = TreeNode(3)
root.right = TreeNode(10)
root.left.left = TreeNode(1)
root.left.right = TreeNode(6)
root.left.right.left = TreeNode(4)
root.left.right.right = TreeNode(7)
root.right.right = TreeNode(14)
root.right.right.left = TreeNode(13)
# Perform postorder traversal on the tree
print("Postorder traversal (Example):")
postorder_traversal(root)
Output :
Postorder traversal (Example): 1 4 7 6 3 13 14 10 8
Explanation :
- The Postorder Traversal code visits nodes in a binary tree in a bottom-up fashion.
- It first explores the left subtree, then the right subtree, and finally visits the root node.
- This traversal order is useful for tasks like deleting a tree, as it ensures child nodes are processed before their parents, preventing orphans in the process.
Complexity Analysis of Postorder Traversal
The complexity analysis for Postorder traversal in a tree is as follows:
Time Complexity:
- In the worst-case scenario, the Postorder traversal algorithm visits all nodes in the tree once.
- The time complexity is O(N), where N is the number of nodes in the tree.
Space Complexity (Auxiliary Space):
- The space complexity depends on the maximum depth (height) of the tree.
- In the worst case, when the tree is skewed (all nodes form a single branch), the space complexity is O(N) due to the recursive function calls, as it requires space on the function call stack for each node.
- In a balanced tree, where the height is log(N), the space complexity is O(log(N)).
Breadth-First Traversal (BFS)
Breadth-first traversal explores all the nodes at the current level before moving on to the nodes at the next level. It uses a queue data structure to keep track of the nodes to be visited. Breadth-first traversal is helpful when you need to find the shortest path between two nodes in a tree or when you want to process levels of a tree sequentially.
Example :
Boundary Traversal
Boundary traversal is a specialized tree traversal technique used with binary trees, a type of tree data structure where each node has at most two child nodes: a left child and a right child. In boundary traversal, we aim to visit and process the nodes lying on the boundary of the binary tree in a specific order. The boundary of a binary tree includes three main components: the left boundary, the leaf nodes, and the right boundary.
Boundary Traversal of the Binary Tree :
Boundary Traversal : 13 ➜ 11 ➜9 ➜ 14 ➜ 16 ➜ 17 ➜ 15
Algorithm for Boundary Traversal :
Boundary traversal is performed in a specific order to ensure that the nodes are visited exactly as described above. The order of boundary traversal can be summarized as follows:
- Start with the root node.
- Traverse the left boundary, excluding the leftmost leaf node.
- Traverse and visit all the leaf nodes from left to right.
- Traverse the right boundary, excluding the rightmost leaf node.
- End with the root node (for full traversal).
Diagonal Traversal
Diagonal traversal is a unique tree traversal technique primarily applied to binary trees. In diagonal traversal, nodes of the binary tree are visited in a diagonal pattern, starting from the top-left diagonal and progressing to the bottom-right diagonal. This traversal explores nodes in a manner that combines both depth-first and breadth-first approaches, providing a different perspective on the tree’s structure.
For Example :
Diagonal Traversal of the Binary Tree :
Diagonal 0 : 13 15 17
Diagonal 1 : 11 12 16
Diagonal 2 : 9 14
Understanding Diagonal Traversal :
Diagonal traversal works by following a set of rules:
- Start at the root node.
- Visit the right child of the current node if it exists.
- Move to the left child of the current node.
- Repeat steps 2 and 3 until there are no more nodes to visit on the current diagonal.
- Move to the next diagonal by following steps 2 and 3, and repeat the process until all diagonals are traversed.
Applications of Tree Traversal in Data Structure
Tree traversal algorithms have a wide range of applications in computer science and real-world scenarios. Some common applications include:
To Wrap it up:
In conclusion, Tree Traversal in Data Structure plays a crucial role in exploring and processing tree-like structures efficiently. Whether it’s the depth-first traversal methods like preorder, inorder, and postorder, or the breadth-first traversal, they enable us to access and manipulate data stored in trees. Tree traversal in Data Structure is not only a fundamental building block but also a key tool for solving complex problems involving hierarchical data structures.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Question 1.
Why is tree traversal important?
Tree traversal is important because it allows us to access and manipulate data stored in hierarchical structures efficiently. It serves as a fundamental tool for various algorithms and applications.
Question 2.
What is the difference between preorder, inorder, and postorder traversal?
Preorder visits the current node before its children, inorder visits the left subtree, then the current node, and postorder visits the children before the current node.
Question 3.
What is breadth-first traversal, and when is it used?
Breadth-first traversal explores nodes level by level, and it is often used to find the shortest path or to perform level-order processing.
Question 4.
How does diagonal traversal differ from other traversal methods?
Unlike traditional traversal methods like preorder or inorder, diagonal traversal follows diagonal paths, combining depth-first and breadth-first approaches.
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment