Tree Traversal is described as the process of travelling across all the nodes in a tree data structure such that no node is left unvisited in the path. There are different ways to travel in a tree, namely, Inorder Traversal, Preorder Traversal and Postorder Traversal.
What is a Tree?
A tree is a hierarchical data structure that is undirected and nodes are stored in a level-wise order. The noot at the top of the tree is known as the root node while the immediate predecessor and immediate successor are termed the parent and child node.
The two nodes with the same parent node are known as siblings. Another important terminology to know is a leaf node, a node that has no children. Below is an illustration that can help you understand the tree data structure well to proceed with traversals that can be performed.
Inorder Traversal
In this form of traversal, the nodes are traversed such that the sequence is in increasing or non-decreasing order. Left->Root->Right pattern is followed to traverse the nodes as we can go as further to left until there is no left or smaller value to pick from.
On returning back to the parent node, the nodes of the right are traversed in a similar manner and the pattern follows for each node in the tree until we are done traversing the tree.
Dry Run of Inorder Traversal
Taking an example of the given tree below, we go over step by step to see how the inorder traversal is performed on a tree.
We keep moving to the left till there is no left element.
As we see in the above figure, 0 is the smallest and there is no element smaller than that on left, we output and go back.
Moving to the right subtree, we go on from 2 to 5 printing 2 is the process.
Being on the leaf node, we can no longer go further thus, print 5 and return back to the parent node.
Having completed the left subtree of the node we return to the node successfully to travel further.
Printing 9 or the root node and diving to the right subtree, we head to node value 12 on the right.
Going as further to left in the subtree, we step towards the next node on the left.
As we are currently on leaf node, we return back as we are out of path.
Completing the left subtree of node with value 12, we print the value and traverse to the right.
We print and return back to the initial or node to finish the process of Inorder Traversal
Algorithm of Inorder Traversal
- Starting at the left subtree, the Inorder function is called on it.
- The root node is then visited.
- Lastly, the Inorder function is called on the right subtree.
Preorder Traversal
In the preorder traversal of a binary tree, the nodes are visited in the following sequence: Root->Left->Right. The algorithm starts by visiting or printing the root node, and then traversing the left subtree.
Once the left subtree has been fully traversed, the algorithm then moves on to traverse the right subtree. This pattern is repeated for each node in the tree until all nodes have been visited. In this way, the preorder traversal visits the root node first, followed by the left subtree, and finally the right subtree. This pattern allows for a quick traversal of the entire tree, starting from the root and moving down towards the leaves.
Algorithm for Preorder Traversal
- Visit the root node.
- Traverse the left subtree by recursively calling the preorder function on the left child.
- Traverse the right subtree by recursively calling the preorder function on the right child.
Dry Run of Preoder Traveral
Looking in a step by step manner onhow we can solve the preorer traversal.
Traversing from the root node, we move to the left of 2.
Going from the node 0, we found nothing, so returning back to the parents.
On returing to noe with value 2 from left subree, we move to the right subtree.
As, 5 is visited, we add it to visited or print it and move back as it is a leaf node.
Now moving back to the root node as the left subtree from root is already traversed successfully.
Now moving forward the right part of the root node.
We go deep down to the left node attached to the node with value 12.
As the current node, being a leaf node, we return back to the parent.
On moving to the right subtree of node with value 12, we encounter 16.
Now that we are done with the preorder traversal, we return back to the node to wind up our traversal.
Postorder Traversal
In the postorder traversal of a binary tree, the nodes are visited in the following sequence: Left->Right->Root.
The algorithm starts by visiting or traversing the left subtree, then moving on to traverse the right subtree. Once the right subtree has been fully traversed, the algorithm then visits the root node. This pattern is repeated for each node in the tree until all nodes have been visited.
In this way, the postorder traversal visits the left subtree first, followed by the right subtree, and finally the root node. This pattern allows for a quick traversal of the entire tree, starting from the leaves and moving up towards the root.
Algorithm for Postorder Traversal
- Traverse the left subtree by recursively calling the postorder function on the left child.
- Traverse the right subtree by recursively calling the postorder function on the right child.
- Visit the root node.
Dry Run of Postorder Traversal
Starting the traversal from the root node towards the left side of the tree.
We hop onto the node having value 0 from the node having value 0.
As 0 is a leaf node, By the concept of Left-Right-Root, we add 0 to visited or print in our case to the output.
Jumping towards the right subtree of 2, we traverse to 5.
Being another leaf node, we print 5 in the process.
On completing the left subtree of the root node, we return back to the position where we started.
Covering the right half of the subtree, we start to traverse towards 12.
Traversing to left from node with value 12 to node with value 11.
Being a leaf node, we print 11 and return back to its parents.
Now hopping onto the right subtree of the node with value 12, we move towards 16.
Being a leaf node, we will print the value and keep returning back with keeping in mind to print the value.
12 is printed as we are done with traversing the left and right subtrees of the node.
The root node is visited at the very end according to the traversal technique of Postorder Traversal. In this process, we are done with Postorder Traversal.
Code for Tree Traversals
As we have seen the algorithm and dry run for each of the three techniques, now let us look at the code to implement all three traversals, Inorder Traversal, Postorder Traversal and Preorder Traversal in an iterative and recursive manner.
Here is an implementation of the iterative code for inorder, postorder, and preorder traversals in Python, using the binary tree with values 9, 2, 12, 0, 5, 11, and 16.
Link to Iterative Code:
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
# Create the binary tree
root = TreeNode(9)
root.left = TreeNode(2)
root.right = TreeNode(12)
root.left.left = TreeNode(0)
root.left.right = TreeNode(5)
root.right.left = TreeNode(11)
root.right.right = TreeNode(16)
# Inorder Traversal
def inorderTraversal(root):
result, stack = [], []
while True:
while root:
stack.append(root)
root = root.left
if not stack:
return result
node = stack.pop()
result.append(node.val)
root = node.right
# Postorder Traversal
def postorderTraversal(root):
result, stack = [], [(root, False)]
while stack:
node, visited = stack.pop()
if node is None:
continue
if visited:
result.append(node.val)
else:
stack.append((node, True))
stack.append((node.right, False))
stack.append((node.left, False))
return result
# Preorder Traversal
def preorderTraversal(root):
result, stack = [], [root]
while stack:
node = stack.pop()
if node is None:
continue
result.append(node.val)
stack.append(node.right)
stack.append(node.left)
return result
# Print the results
print("Inorder Traversal:", inorderTraversal(root))
print("Postorder Traversal:", postorderTraversal(root))
print("Preorder Traversal:", preorderTraversal(root))
Output:
Inorder Traversal: [0, 2, 5, 9, 11, 12, 16]
Postorder Traversal: [0, 5, 2, 11, 16, 12, 9]
Preorder Traversal: [9, 2, 0, 5, 12, 11, 16]Link to Recursive Code:
# your code goes here
# your code goes here# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def inorderTraversal(root: TreeNode):
res = []
def helper_inorder(node):
if not node:
return
helper_inorder(node.left)
res.append(node.val)
helper_inorder(node.right)
helper_inorder(root)
return res
def postorderTraversal(root: TreeNode):
res = []
def helper_postorder(node):
if not node:
return
helper_postorder(node.left)
helper_postorder(node.right)
res.append(node.val)
helper_postorder(root)
return res
def preorderTraversal(root: TreeNode):
res = []
def helper_preorder(node):
if not node:
return
res.append(node.val)
helper_preorder(node.left)
helper_preorder(node.right)
helper_preorder(root)
return res
# Example usage with input tree [9, 2, 12, 0, 5, 11, 16]
root = TreeNode(9)
root.left = TreeNode(2)
root.right = TreeNode(12)
root.left.left = TreeNode(0)
root.left.right = TreeNode(5)
root.right.left = TreeNode(11)
root.right.right = TreeNode(16)
print("Inorder Traversal:",inorderTraversal(root))
print("Postorder Traversal:",postorderTraversal(root))
print("Prerder Traversal:",preorderTraversal(root))
Output:
Inorder Traversal: [0, 2, 5, 9, 11, 12, 16]
Postorder Traversal: [0, 5, 2, 11, 16, 12, 9]
Preorder Traversal: [9, 2, 0, 5, 12, 11, 16]Conclusion
In this article, we started with studying what are trees and what traversal techniques are used and proceeded with algorithm and a dry run for inorder traversal, postorder traversal and preorder traversal. We implemented the iterative and recursive code for all three traversals. The time complexity of these traversals is O(n) and talking of space complexity, it is O(n) unless the stack is not used for recursion.
Frequently Asked Questions
1. What is tree traversal?
Tree traversal is the process of visiting each node in a tree data structure in a specific order. There are three common orders of tree traversal: inorder, postorder, and preorder. In each of these traversals, the algorithm starts at the root node and visits its children in a specific order, before moving on to its siblings.
2. What is the difference between inorder, postorder, and preorder traversal?
In inorder traversal, the nodes are visited in the order left child, root, right child. In postorder traversal, the nodes are visited in the order left child, right child, root. In preorder traversal, the nodes are visited in the order root, left child, and right child. The choice of traversal order depends on the specific requirements of the problem being solved.
3. How is tree traversal implemented?
Tree traversal can be implemented using either a recursive or an iterative approach. In a recursive approach, the algorithm uses nested function calls to traverse the tree, visiting each node and its children in a specific order. In an iterative approach, the algorithm uses a stack data structure to keep track of which nodes need to be visited next.
4. When is tree traversal used?
Tree traversal is used in a variety of algorithms and data structures that involve trees, such as searching for a specific node in the tree, finding the lowest common ancestor of two nodes, or evaluating mathematical expressions stored in a binary tree. It is also used in tree data structures for processing and manipulating hierarchical data, such as XML or JSON files.