Tree Traversal : Inorder, Preorder and Postorder

Last Updated on November 1, 2023 by Ankit Kochar

Tree traversal refers to the procedure of navigating through all the nodes within a tree data structure, ensuring that every node is visited along the way. Various methods of traversing a tree include Inorder Traversal, Preorder Traversal, and Postorder Traversal.

What is a Tree?

A tree is a hierarchical data structure characterized by its non-directional nature, with nodes organized in a hierarchical, level-based order. The uppermost node in the tree is referred to as the root node, and nodes that are directly connected above and below it are known as the parent and child nodes, respectively.

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

1. Starting at the left subtree, the Inorder function is called on it.
2. The root node is then visited.
3. 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

1. Visit the root node.
2. Traverse the left subtree by recursively calling the preorder function on the left child.
3. 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

1. Traverse the left subtree by recursively calling the postorder function on the left child.
2. Traverse the right subtree by recursively calling the postorder function on the right child.
3. 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 conclusion, tree traversal, encompassing Inorder, Preorder, and Postorder traversal methods, is a fundamental concept in working with tree data structures. These traversal techniques enable the systematic exploration of all nodes within a tree, ensuring that each node is visited precisely once. Tree traversal plays a pivotal role in a wide range of computer science applications, including data retrieval, searching, and tree-based algorithms.

Frequently Asked Questions related to Tree Traversal : Inorder, Preorder and Postorder:

Here are some of the FAQs related to Tree Traversal : Inorder, Preorder and Postorder

1. Why is tree traversal important in computer science?
Tree traversal is vital for accessing and processing data within tree structures efficiently. It’s used in various algorithms, such as searching, sorting, and parsing, and plays a crucial role in data retrieval.

2. What is the significance of the root node in a tree structure?
The root node is the topmost node in a tree and serves as the entry point for accessing all other nodes. It defines the hierarchical structure and relationships within the tree.

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.

5. Are there variations or optimizations of tree traversal algorithms?
Yes, there are variations and optimizations of tree traversal algorithms, including iterative and recursive implementations, as well as Morris Traversal for binary trees, which reduces space complexity. The choice of method depends on specific use cases and requirements.