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:

Step	Action	Explanation
1	Go left from 1 → 2 → 4	Keep going left until there is no left child
2	Visit 4	Node 4 has no left child, so it is visited first
3	Visit 2	Left subtree of 2 is done, so visit 2 itself
4	Go right from 2 → 5	Move to right child of 2
5	Visit 5	Node 5 has no children, so it is visited
6	Visit 1	Left subtree of 1 is complete, so visit the root
7	Go right from 1 → 3	Move to right subtree of 1
8	Visit 3	Node 3 has no left child, so it is visited
9	Go right from 3 → 6	Move to right child of 3
10	Visit 6	Node 6 has no children, so it is visited

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

    # Step 1: Traverse the left subtree
    inorder_traversal(node.left)

    # Step 2: Visit the current node
    print(node.data, end=' ')

    # Step 3: Traverse the right subtree
    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__':
    # Build the tree:
    #         1
    #        / \
    #       2   3
    #      / \   \
    #     4   5   6

    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)


# Example of Usage

# Build the tree:
#         1
#        / \
#       2   3
#      / \   \
#     4   5   6

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 efficient list-building approach

The version above creates many intermediate lists due to concatenation. For better performance on large trees, use a helper with an accumulator:

def inorder_to_list(node):
    """Efficiently collect inorder traversal into a list."""
    result = []

    def _traverse(n):
        if n is None:
            return
        _traverse(n.left)
        result.append(n.data)
        _traverse(n.right)

    _traverse(node)
    return result

Output:

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

This avoids creating and merging intermediate lists, reducing overhead from O(n²) to O(n).

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.

#       4
#      / \
#     2   6
#    / \ / \
#   1  3 5  7

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 

Comparison with other traversals

Traversal	Order	Common Use Cases
Inorder	Left → Root → Right	Sorted output from BST, expression evaluation
Preorder	Root → Left → Right	Tree copying, serialization, prefix expressions
Postorder	Left → Right → Root	Tree deletion, postfix expressions, dependency resolution

Time and Space Complexity

Aspect	Complexity	Explanation
Time	O(n)	Every node is visited exactly once, where n is the total number of nodes
Space (best case)	O(log n)	For a balanced tree, the recursion depth equals the tree height
Space (worst case)	O(n)	For a completely skewed tree (essentially a linked list), the recursion depth equals n

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.

Watch out for stack overflow on very deep trees

For extremely deep or skewed trees (e.g., 10,000+ nodes in a chain), Python's default recursion limit (usually 1,000) will cause a RecursionError. You can increase the limit with sys.setrecursionlimit(), but a better approach for very deep trees is to use an iterative inorder traversal with an explicit stack.

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.