Tree traversal refers to the process of going through a tree data structure and checking out each node. Different methods of tree walking exist, each with its own set of advantages and disadvantages, that are determined by the needs of the user. Common examples of tree traversal include:
Breadth-First Search (BFS)
When searching a tree, the Breadth-First Search (BFS) method ensures that every node on the current depth level gets explored before going on to the next. BFS utilises a queue data structure to keep track of the nodes to be visited, beginning at the root node. It’s helpful when you want to go through the tree’s branches one at a time.
BFS can be split into two categories:
1. Level Order Traversal
2. Reverse Level Order Traversal
Level Order Traversal
This approach goes over the nodes in a hierarchical graph from left to right. The queue data structure is used to accomplish this function. Each child node in the tree is added to the queue after the root node in the order in which they appear in the tree. The queue’s head item is dequeued, and its offspring are appended to the queue. Repeat this step until there are no more items in the queue.
Reverse Level Order Traversal
This is similar to Level Order Traversal, except that it visits the nodes in reverse level order, starting from the last level and moving toward the root node.
For example, consider the following binary tree:
1
/ \
2 3
/ \ \
4 5 6
This traversal would go from node 1 to node 6 in the order listed above, in level order. The algorithm traverses the tree from the root node (1) through the leaf nodes (2) and (3) and finally the terminal nodes (4). (4, 5, 6).
Swap The Levels Around Following this traversal, the nodes would be visited in this order: 4, 5, 6, 3, 2, 1. The method traverses the tree from the outermost levels (4,5,6) to the innermost levels (3), then back to the root node (1).
Note that while queues are the most common data structure for implementing BFS, recursion can also be used, however at the expense of efficiency.
Depth-First Search (DFS)
In depth-first search (DFS), an algorithm traverses a graph by first going to the farthest point it can along each branch, then going back to the root node. The method relies on the stack data structure to remember which vertex it should proceed to next.
The two most common forms of DFS are:
1. Recursive DFS
2. Iterative DFS
Recursive DFS:
It uses the recursion stack to keep track of the next vertex to visit. The recursive implementation of DFS is a simple and intuitive method to traverse a graph. In this method, the algorithm visits a vertex, marks it as visited, and recursively calls the DFS function on all adjacent vertices.
Iterative DFS:
It uses an explicit stack to keep track of the next vertex to visit. The iterative DFS uses a stack data structure to keep track of the vertices to be visited next. The algorithm starts at the root node and pushes it onto the stack. It then visits the vertex at the top of the stack and pushes all its unvisited children onto the stack. The process continues until the stack is empty.
Example: Consider the below graph:
1 / \ 2 3 / \ / \ 4 5 6 7
This is a binary tree with 7 nodes. The root node is 1, with left and right children 2 and 3 respectively. Node 2 has left and right children 4 and 5, respectively. Similarly, Node 3 has left and right children 6 and 7 respectively.
This tree can be represented in the form of an adjacency list as:
1: [2, 3] 2: [4, 5] 3: [6, 7] 4: [] 5: [] 6: [] 7: []
There are three types of DFS traversals in a tree:
- Inorder traversal
- Preorder traversal
- Postorder traversal
Inorder Traversal
Inorder traversal is a method of traversing a binary tree. The left subtree of a binary tree is reached first in inorder traversal, followed by the root node, and finally the right subtree. The terms “depth-first search” and “symmetric order” are also used to describe this procedure. In a binary tree, nodes are visited in the order of left-root-right during inorder traversal. This enables us to organize our visits to the nodes and our subsequent processing of them.
Since Inorder traversal visits nodes in a left-root-right fashion, it is best suited for cases where you need the nodes to be returned in sorted order. The items can be searched, sorted, and printed in a predetermined order, among other uses.
Stacks and recursion are used to implement inorder traversal. The recursive approach begins with a walk through the left subtree, continues to the root node, and then finishes with a walk through the right subtree. The stack approach begins with an empty stack, which is then filled by adding the root node and proceeding with the following steps until the stack is empty. To do this, we’ll first remove a node from the stack, then pay it a visit, and finally add that node’s right and left children to the stack.
Many algorithms in DSA rely on inorder traversal since it is both straightforward and practical for navigating binary trees. Any student of DSA would do well to learn and practise this traversal approach because it serves as a foundation for comprehending more advanced algorithms and data structures.
Preorder Traversal
When following a preorder traversal algorithm on a binary tree, the first node visited is the root, then the left subtree, and finally the right subtree. A depth-first search or preorder traversal are other names for this strategy. Specifically, the nodes of a binary tree are traversed in the preorder of root, left, right.
When processing the root node before its children is necessary, preorder traversal is the method of choice. When making a duplicate of a tree, preorder traversal is often put to use, with the root node being handled before any of its children. Algorithms for parsing expressions, compiling expressions, and serialising trees all make use of preorder traversal.
The use of recursion or a stack allows for preorder traversal to be implemented. The recursive approach begins at the root node and continues to the left subtree before moving on to the right. The stack approach begins with an empty stack, which is then filled by adding the root node and proceeding with the following steps until the stack is empty. You can do this by popping a node off the stack, then visiting it, and then pushing its right and left children onto the stack in the opposite sequence.
Many algorithms in DSA rely on preorder traversal since it is both straightforward and practical for navigating binary trees. Any student of DSA would do well to learn and practise this traversal approach because it serves as a foundation for comprehending more advanced algorithms and data structures.
Postorder Traversal
Postorder traversal is a method of traversing a binary tree, where the left subtree is visited first, then the right subtree, and finally the root node. This method is also known as a “depth-first search” or “postorder” traversal. The postorder traversal of a binary tree visits the nodes in a specific order, which is left-right-root.
Postorder traversal is mostly used in scenarios where both subtrees need to be processed before the root node, this is because the order of visiting the nodes is left-right-root. A common use case of postorder traversal is in deleting a tree, in this case the children are deleted first and then the root. Also, postorder traversal is used in algorithms such as converting infix notation to postfix notation and evaluating postfix expressions.
Postorder traversal is implemented using recursion or using a stack. The recursive method involves traversing the left subtree first, then traversing the right subtree, and finally visiting the root node. The stack method involves creating an empty stack, pushing the root node onto the stack, and then repeating the following steps until the stack is empty: pop a node from the stack, visit the node, and push the left and right children of the node onto the stack in reverse order.
Postorder traversal is a simple and useful method for traversing a binary tree, and it’s a fundamental building block for many algorithms in DSA. Understanding and implementing this traversal method is essential for any student studying DSA, as it will help them to understand more complex algorithms and data structures.
So, we can solve the above graph as follows:
In Order Traversal
Inorder traversal is a way to visit all the nodes of a binary tree by visiting the left subtree first, then the root node, and finally the right subtree.
To start, we begin at the leftmost node of the tree, which in this case is node 4.
We visit this node and print its value, which is 4.
Next, we move to the left child of node 4, which is null. Since there is no left child, we backtrack and move to the right child of node 4, which is also null.
Since there are no more children to visit, we backtrack again to the parent node of 4, which is node 2.
We visit node 2 and print its value, which is 2.
Next, we move to the left child of node 2, which is node 5.
We visit node 5 and print its value, which is 5.
Next, we move to the left child of node 5, which is null.
Since there is no left child, we backtrack and move to the right child of node 5, which is also null.
Since there are no more children to visit, we backtrack again to the parent node of 5, which is node 1.
We visit node 1 and print its value, which is 1.
Next, we move to the left child of node 1, which is node 6.
We visit node 6 and print its value, which is 6.
Next, we move to the left child of node 6, which is null.
We visit node 7 and print its value, which is 7.
Next, we move to the left child of node 7, which is null.
Since there is no left child, we backtrack and move to the right child of node 7, which is also null.
Since there are no more children to visit, we backtrack again to the parent node of 7, which is node 3.
We visit node 3 and print its value, which is 3.
Since node 3 is the root node, there are no more nodes to visit, so the in-order traversal is complete.
The sequence of nodes visited in the in-order traversal would be 4-2-5-1-6-3-7.
Preorder traversal of the binary tree
Preorder traversal is a way to visit all the nodes of a binary tree by visiting the root node first, then the left subtree, and finally the right subtree.
To start, we begin at the root node of the tree, which in this case is node 1.
We visit this node and print its value, which is 1.
Next, we move to the left child of node 1, which is node 2.
We visit node 2 and print its value, which is 2.
Next, we move to the left child of node 2, which is node 4.
We visit node 4 and print its value, which is 4.
Next, we move to the left child of node 4, which is null.
Since there is no left child, we backtrack and move to the right child of node 4, which is also null.
Since there are no more children to visit, we backtrack again to the parent node of 4, which is node 2.
Next, we move to the right child of node 2, which is node 5.
We visit node 5 and print its value, which is 5.
Next, we move to the left child of node 5, which is null.
Since there is no left child, we backtrack and move to the right child of node 5, which is also null.
Since there are no more children to visit, we backtrack again to the parent node of 5, which is node 1.
Next, we move to the right child of node 1, which is node 3.
We visit node 3 and print its value, which is 3.
Next, we move to the left child of node 3, which is node 6.
We visit node 6 and print its value, which is 6.
Next, we move to the left child of node 6, which is null.
Since there is no left child, we backtrack and move to the right child of node 6, which is node 7.
We visit node 7 and print its value, which is 7.
Next, we move to the left child of node 7, which is null.
Since there is no left child, we backtrack and move to the right child of node 7, which is also null.
Since there are no more children to visit, we backtrack again to the parent node of 7, which is node 3.
Since node 3 is the root node, there are no more nodes to visit, so the preorder traversal is complete.
The sequence of nodes visited in the preorder traversal would be 1-2-4-5-3-6-7.
Postorder traversal for the Binary Tree
Postorder traversal is a way to visit all the nodes of a binary tree by visiting the left subtree first, then the right subtree, and finally the root node.
To start, we begin at the left child of the root node, which in this case is node 2.
Next, we move to the left child of node 2, which is node 4.
We visit node 4 and print its value, which is 4.
Next, we move to the left child of node 4, which is null.
Since there is no left child, we backtrack and move to the right child of node 4, which is also null.
Since there are no more children to visit, we backtrack again to the parent node of 4, which is node 2.
Next, we move to the right child of node 2, which is node 5.
We visit node 5 and print its value, which is 5.
Next, we move to the left child of node 5, which is null.
Since there is no left child, we backtrack and move to the right child of node 5, which is also null.
Since there are no more children to visit, we backtrack again to the parent node of 5, which is node 2.
Now we visit node 2 and print its value, which is 2.
Next, we move to the parent node of 2, which is node 1.
Next, we move to the right child of node 1, which is node 3.
Next, we move to the left child of node 3, which is node 6.
Next, we move to the left child of node 6, which is null.
Since there is no left child, we backtrack and move to the right child of node 6, which is node 7.
We visit node 7 and print its value because there is no child further. Since there are no more children to visit, we backtrack again to the parent node of 7, which is node 6.
We visit node 6 and print its value, which is 6.
Next, we move to the parent node of 6, which is node 3.
We visit node 3 and print its value, which is 3.
Finally, we move to the parent node of 3, which is the root node 1.
We visit node 1 and print its value, which is 1.
At this point, we have visited all the nodes of the binary tree in postorder traversal order. The sequence of nodes visited would be 4-5-2-7-6-3-1.
The postorder traversal is a way to visit all the nodes of a binary tree, this is used in the case of the expression tree where the postorder traversal gives the expression in the reverse polish notation and also it is used to delete the tree because in this traversal we can delete the leaf node first and then the parent node.
So the results will be:
- In order traversal: The sequence of nodes visited would be 4-2-5-1-6-3-7.
- Preorder traversal: The sequence of nodes visited would be 1-2-4-5-3-6-7.
- Postorder traversal: The sequence of nodes visited would be 4-5-2-6-7-3-1.
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def inorder(root):
if root:
inorder(root.left)
print(root.data)
inorder(root.right)
Here’s an example of a Python implementation of the DFS algorithm for preorder traversal:
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def preorder(root):
if root:
print(root.data)
preorder(root.left)
preorder(root.right)
Here’s an example of a Python implementation of the DFS algorithm for postorder traversal:
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def postorder(root):
if root:
postorder(root.left)
postorder(root.right)
print(root.data)
Full code implementation of Tree Traversal in Python Using Recursion
# Definition of the Node class
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# Inorder traversal function
def inorder(root):
if root:
inorder(root.left)
print(root.data)
inorder(root.right)
# Preorder traversal function
def preorder(root):
if root:
print(root.data)
preorder(root.left)
preorder(root.right)
# Postorder traversal function
def postorder(root):
if root:
postorder(root.left)
postorder(root.right)
print(root.data)
# Creating the binary tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
# Print instructions
print("Instructions:")
print("Enter 1 for inorder traversal")
print("Enter 2 for preorder traversal")
print("Enter 3 for postorder traversal")
# Input
choice = int(input("Enter your choice: "))
# Output
if choice == 1:
print("Inorder traversal:")
inorder(root)
elif choice == 2:
print("Preorder traversal:")
preorder(root)
elif choice == 3:
print("Postorder traversal:")
postorder(root)
else:
print("Invalid choice")
The binary tree is constructed after the Node class is defined in this code. Then, it specifies three recursive functions for tree traversal in inorder, preorder, and postorder.
Manually constructing instances of the Node class and then linking them together to make the tree is how the binary tree is constructed.
The user is then given the option to select the traversal type they wish to utilise by entering 1, 2, or 3. (inorder, preorder, or postorder). The user’s selection is saved in the “choice” variable, and that value is later utilised to determine which traversal function should be invoked.
The code will output “Invalid choice” if the user selects an invalid option.
The code, when run, presents the user with a series of options and, depending on which one is selected, either performs a preorder or postorder tree traversal or prints the data from each node visited in the order in which it was visited.
The time complexity of tree traversal using recursion in Python is O(n), where n is the number of nodes in the tree. This is because, in each traversal method, we visit every node in the tree exactly once. In the worst-case scenario, we have to traverse all the nodes of the tree, and thus the time complexity is linear, i.e., O(n).
Similarly, the space complexity of the algorithm is O(n) as well. This is because, during the traversal, we use the call stack to store the function calls, and in the worst-case scenario, we might have to store all the function calls corresponding to all the nodes in the tree. As the number of nodes in the tree is n, the space complexity is also linear, i.e., O(n).
In summary, the algorithm has a time complexity of O(n) and a space complexity of O(n), making it an efficient algorithm for traversing a tree structure in Python using recursion.
Where it's used?
The inorder traversal method is commonly used for sorting algorithms and binary search trees due to its ability to traverse a tree in a non-decreasing order of nodes. It starts at the left leaf node and works its way to the root before moving on to the right branch.
However, the preorder traversal approach is used to get the prefix expression of an expression tree and to make a duplicate of the tree. The first node it goes to is the root, then the left and right branches. This technique is often utilized by compilers and parser algorithms.
To delete a tree from an expression graph or to extract its postfix expression, the postorder traversal technique is utilized. Before reaching the root node, it travels to the immediate left and right branches. The leaves of a tree can be processed first using this method, making it ideal for tree traversals that have to do so.
Conclusion
Understanding tree traversal is essential for programmers because of its practicality in many contexts. Within its pages, this article has discussed the many recursive tree traversals that can be implemented in Python and their respective applications. We have also included the Python source code and the results for each traversal technique, so you can see how they function and make better use of them.
