Inorder Traversal of Binary Tree

Algorithm for Inorder Traversal of Binary Tree

The algorithm for inorder traversal of a binary tree is : 

Algorithm inorderTraversal(root)
   if root is null then
       return
   
   inorderTraversal(root.left)
   visit(root)
   inorderTraversal(root.right)

The `inorderTraversal` function takes the root node of the binary tree as input and performs the following steps:

1. Check if the `root` is null. If it is, return from the function since an empty tree or a null subtree has no nodes to traverse.

2. Recursively call `inorderTraversal` on the left subtree of the current `root` node by passing `root.left` as the argument. This step traverses the left subtree of the current node.

3. Visit the current `root` node. This is where you perform any desired operation on the node, such as printing its value or adding it to a list.

4. Recursively call `inorderTraversal` on the right subtree of the current `root` node by passing `root.right` as the argument. This step traverses the right subtree of the current node.

The algorithm follows the Left-Node-Right order, meaning it first traverses the left subtree, then visits the current node, and finally traverses the right subtree.

Let's see the Python code that implements the inorder traversal algorithm:

• Python

Python

class TreeNode:
   def __init__(self, value):
       self.val = value
       self.left = None
       self.right = None

def inorderTraversal(root):
   if root is None:
       return

   inorderTraversal(root.left)
   print(root.val, end=" ")
   inorderTraversal(root.right)

# Example usage
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
root.right.left = TreeNode(5)
root.right.right = TreeNode(7)

print("Inorder traversal:")
inorderTraversal(root)

You can also try this code with Online Python Compiler

Run Code

Output:

Inorder traversal:
1 2 3 4 5 6 7

In this code, the `TreeNode` class represents a node in the binary tree, and the `inorderTraversal` function implements the inorder traversal algorithm. The function recursively traverses the left subtree, prints the value of the current node, and then traverses the right subtree.

Note: The code assumes that the binary tree is properly constructed with valid left and right child references.

How Does Inorder Traversal of Binary Tree Work?

Inorder traversal is a method to process & examine each node in a binary tree. This process ensures each node is visited in a non-decreasing order. To achieve this, the traversal follows a specific pattern: it first visits the left subtree, then the node itself, & finally, the right subtree.

Let's see with a simple binary tree:

• Start at the Root: Begin at the root node of the tree.
   
• Visit Left Subtree: Before looking at the root node's value, traverse its left subtree using the same inorder method. This means you keep going left until you reach a leaf, the end point of a branch.
   
• Visit Node: Once the left subtree is fully traversed, process the current node. You can now record or print the node's value.
   
• Visit Right Subtree: After the node, move to its right subtree & repeat the inorder traversal process.
   

Let's consider an example binary tree to understand the inorder traversal process better:

The inorder traversal of this binary tree would be: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7

As you can see, the nodes are visited in ascending order of their values, which is a characteristic of inorder traversal in a binary search tree.

Note -: This method is especially useful because it processes the tree nodes in an ascending order, which is practical for various applications like sorting & constructing ordered lists.

Program to Implement Inorder Traversal of Binary Tree

Here’s a basic structure of a binary tree node in Python:

class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

This TreeNode class creates nodes of the binary tree where value holds the data, & left and right point to the left & right children of the node.

Now, let's define the function to perform inorder traversal:

def inorder_traversal(root):
    # This list will hold the order of visited nodes
    res = []
    # Helper function to traverse the tree
    def traverse(node):
        if node:
            # First visit the left child
            traverse(node.left)
            # Then visit the node itself
            res.append(node.value)
            # Finally, visit the right child
            traverse(node.right)
    # Start the traversal from the root
    traverse(root)
    return res

To use this function, we need to create a binary tree. Let’s create a simple binary tree:

# Creating nodes
node1 = TreeNode(1)
node2 = TreeNode(2)
node3 = TreeNode(3)

# Linking nodes (Assuming node2 is the root)
node2.left = node1
node2.right = node3

# Now let's perform the inorder traversal
print(inorder_traversal(node2))  # Output will be [1, 2, 3]

This example shows how the nodes are visited in the order of their values from smallest to largest. This simple program can be expanded or modified to handle more complex trees & operations.

Complexity Analysis of Inorder Traversal

When we discuss complexity analysis in the context of inorder traversal, we focus on two main aspects: time complexity and space complexity. Understanding these concepts helps us identify how efficient our traversal method is, depending on the size and structure of the binary tree.

Time Complexity

The time complexity of inorder traversal is O(n), where n is the number of nodes in the binary tree. This is because each node in the tree is visited exactly once. Regardless of the tree’s shape—whether it's balanced or skewed—the traversal covers every node, ensuring complete processing.

Space Complexity

The space complexity primarily depends on the height of the tree, which affects the recursion stack. In the best-case scenario, where the tree is balanced, the height of the tree would be log(n), leading to a space complexity of O(log(n)). This is because a balanced tree reduces the amount of recursive calls stacked during the traversal.

In the worst case, if the tree becomes a skewed tree (resembling a linked list with nodes connected to only one child), the space complexity degrades to O(n). This happens because the recursion stack will hold a pointer for each node due to the tree's height equaling the number of nodes.

Use Cases of Inorder Traversal

Binary Search Trees (BSTs

In a binary search tree, inorder traversal retrieves elements in a sorted order. This property is particularly useful when you need an ordered list of elements, which can be beneficial for tasks that require sorted data, like binary search.

Graphical User Interfaces

In GUI applications that display structured data, such as file systems or organizational charts, inorder traversal can be used to display items in a specific order. This helps in maintaining logical arrangement and hierarchy in the display.

Syntax Trees

In compilers, inorder traversal is used to generate a linear sequence of code elements from a syntax tree. This sequence helps in the translation and compilation processes, ensuring that the derived code matches the source code’s intended functionality.

Data Recovery

For databases that implement binary trees, inorder traversal can help in data recovery processes. By traversing the tree structure systematically, one can recover records in their logical order, which is crucial after system failures or corruptions.

Debugging

Developers use inorder traversal to debug and validate the structure of binary trees. Seeing the nodes in a non-decreasing order can help quickly identify issues with node placements, especially in complex data structures.

Frequently Asked Questions

What makes inorder traversal unique compared to other tree traversal methods?

Inorder traversal is unique because it processes nodes in a non-decreasing order, which is especially useful for binary search trees where this order corresponds to the natural order of the elements.

Can inorder traversal be used on non-binary trees?

Inorder traversal is specifically designed for binary trees. For trees with more than two children per node, other traversal methods, such as level-order traversal or depth-first search techniques, are more appropriate.

Is it possible to perform inorder traversal without recursion?

Yes, inorder traversal can be implemented using an iterative approach with a stack. This method involves manually managing the stack to simulate the recursive calls, which some might find more complex but useful in avoiding stack overflow in large trees.

Conclusion

In this article, we have learned about inorder traversal, a fundamental tree traversal technique used extensively in computer science. We saw its basic operation and then we discussed how it works and provided a practical example with a Python program. We understood the time and space complexities to understand its efficiency and concluded with real-world applications that highlight its importance in various programming and data structure tasks. 

You can refer to our guided paths on the Coding Ninjas. You can check our course to learn more about DSA, DBMS, Competitive Programming, Python, Java, JavaScript, etc. Also, check out some of the Guided Paths on topics such as Data Structure andAlgorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry.