How to Implement Inorder Traversal of a Binary Tree in Python

Inorder traversal is one of the three fundamental depth-first traversal techniques for binary trees. It follows the Left → Root → Right pattern: the left subtree is visited first, then the current node is processed, and finally the right subtree is visited.

This traversal order is particularly important because when applied to a Binary Search Tree (BST), it visits all nodes in sorted ascending order, making it essential for tasks like validation, sorting, and range queries.

In this guide, you will learn how inorder traversal works step by step, implement it recursively in Python, and understand its time and space complexity.

How Inorder Traversal Works

The traversal follows three simple rules applied recursively at every node:

1. Traverse the left subtree (recursively apply inorder traversal).
2. Visit the current node (process its data, for example, by printing it).
3. Traverse the right subtree (recursively apply inorder traversal).

The recursion naturally unwinds in the correct order, ensuring that left children are always processed before their parents, and parents before their right children.

Step-by-Step Walkthrough

Consider the following binary tree:

        1
       / \
      2   3
     / \   \
    4   5   6

Here is how inorder traversal processes each node:

Traversal result: 4 → 2 → 5 → 1 → 3 → 6

The Algorithm

The recursive algorithm is elegant and concise:

Inorder(node):
    1. If node is None, return (base case)
    2. Inorder(node.left)        ← traverse left subtree
    3. Process node              ← visit current node
    4. Inorder(node.right)       ← traverse right subtree

The base case (node is None) stops the recursion when we reach a leaf node's non-existent child.

Python Implementation

Defining the Node Class

Each node in the binary tree stores a data value and references to its left and right children:

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

Implementing the Inorder Traversal Function

def inorder_traversal(node):
    """Recursively perform inorder traversal: Left → Root → Right."""
    if node is None:
        return

    inorder_traversal(node.left)

    print(node.data, end=' ')

    inorder_traversal(node.right)

Complete Example

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


def inorder_traversal(node):
    """Recursively perform inorder traversal: Left → Root → Right."""
    if node is None:
        return

    inorder_traversal(node.left)
    print(node.data, end=' ')
    inorder_traversal(node.right)


if __name__ == '__main__':

    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.left.right = Node(5)
    root.right.right = Node(6)

    print("Inorder traversal of binary tree:")
    inorder_traversal(root)

Output:

Inorder traversal of binary tree:
4 2 5 1 3 6 

Returning the Traversal as a List

In practice, you often need the traversal result as a list rather than printed output. Here is a version that collects the values:

def inorder_to_list(node):
    """Return the inorder traversal as a list of values."""
    if node is None:
        return []

    return inorder_to_list(node.left) + [node.data] + inorder_to_list(node.right)




root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.right = Node(6)

result = inorder_to_list(root)
print(result)

Output:

[4, 2, 5, 1, 3, 6]

More Examples

Example 1: Three-Node Tree

    A
   / \
  B   C

root = Node('A')
root.left = Node('B')
root.right = Node('C')

inorder_traversal(root)

Output:

B A C

Example 2: Left-Skewed Tree

    A
   /
  B
 /
D

root = Node('A')
root.left = Node('B')
root.left.left = Node('D')

inorder_traversal(root)

Output:

D B A

Example 3: Five-Node Tree

        A
       / \
      B   C
     / \
    D   E

root = Node('A')
root.left = Node('B')
root.right = Node('C')
root.left.left = Node('D')
root.left.right = Node('E')

inorder_traversal(root)

Output:

D B E A C

Example 4: Empty Tree

inorder_traversal(None)

An empty tree (root is None) produces no output because the base case returns immediately.

Why Inorder Traversal Matters for BSTs

When applied to a Binary Search Tree, inorder traversal visits nodes in sorted order. This property is used for:

• Validating whether a tree is a valid BST.
• Finding the k-th smallest element.
• Converting a BST to a sorted list.

root = Node(4)
root.left = Node(2)
root.right = Node(6)
root.left.left = Node(1)
root.left.right = Node(3)
root.right.left = Node(5)
root.right.right = Node(7)

print("BST inorder (sorted):")
inorder_traversal(root)

Output:

BST inorder (sorted):
1 2 3 4 5 6 7 

Time and Space Complexity

The space complexity comes from the call stack used by the recursive function. Each recursive call adds a frame to the stack, and the maximum depth equals the height of the tree.

Conclusion

Inorder traversal is a fundamental binary tree algorithm that visits nodes in the Left → Root → Right order.

Its recursive implementation in Python is concise, just three lines of logic, and runs in O(n) time with O(h) space, where h is the tree's height.

The traversal is especially significant for Binary Search Trees, where it produces nodes in sorted order.

For practical applications, prefer the accumulator-based approach when collecting results into a list, and consider iterative alternatives for very deep trees to avoid hitting Python's recursion limit.