5 Best Ways to Perform an Inorder Traversal of a Binary Tree in Python

💡 Problem Formulation: Inorder traversal is a fundamental algorithm to process binary trees. It involves visiting the left subtree, the root node, and then the right subtree recursively. In Python, there are several approaches to achieve this. Suppose we have a binary tree; our objective is to visit each node in ascending order per inorder traversal properties. The desired output for a binary tree with nodes 1, 2, and 3 would be: 1, 2, 3.

Method 1: Recursive Inorder Traversal

The first method employs classic recursion to traverse the tree in an inorder manner. This approach is most aligned with the definition of the inorder traversal itself, which naturally exhibits recursive properties.

Here’s an example:

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

def inorder_traversal(root):
  if root:
    inorder_traversal(root.left)
    print(root.value)
    inorder_traversal(root.right)

# Example tree
root = TreeNode(2)
root.left = TreeNode(1)
root.right = TreeNode(3)
inorder_traversal(root)

Output:

1
2
3

This example illustrates the recursive function inorder_traversal which takes a root node and prints the values of the nodes in an inorder fashion. It visits the left child, then the root node, followed by the right child.

Method 2: Iterative Inorder Traversal Using Stack

The second method uses stack data structure to simulate the recursive behavior. It is helpful in situations where system stack size is limited or monitoring the traversal process is required.

Here’s an example:

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

def inorder_traversal_iterative(root):
  stack, result = [], []
  while True:
    while root:
      stack.append(root)
      root = root.left
    if not stack:
      return result
    node = stack.pop()
    result.append(node.value)
    root = node.right

# Example tree
root = TreeNode(2)
root.left = TreeNode(1)
root.right = TreeNode(3)
print(inorder_traversal_iterative(root))

Output:

[1, 2, 3]

The example demonstrates an iterative solution to traverse a binary tree. It uses a stack to keep track of visited nodes and processes them in the correct inorder sequence.

Method 3: Morris Traversal

Morris Traversal is a clever method that achieves inorder traversal without using a stack or recursion, by temporarily modifying the tree.

Here’s an example:

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

def morris_traversal(root):
  current = root
  while current:
    if current.left is None:
      print(current.value)
      current = current.right
    else:
      # Find the inorder predecessor of current
      pre = current.left
      while pre.right is not None and pre.right != current:
        pre = pre.right
      # Make current the right child of its inorder predecessor
      if pre.right is None:
        pre.right = current
        current = current.left
      # Revert the changes made in the tree
      else:
        pre.right = None
        print(current.value)
        current = current.right

# Example tree
root = TreeNode(2)
root.left = TreeNode(1)
root.right = TreeNode(3)
morris_traversal(root)

Output:

1
2
3

The code snippet showcases Morris Traversal where the tree’s structure is temporarily altered to avoid the use of stack or recursion, thus saving memory.

Method 4: Inorder Traversal Using Threads (Threaded Binary Trees)

Threaded binary trees are a variation of binary trees where the null pointers are used to point to the inorder predecessor and successor nodes, enabling us to perform an inorder traversal without stack or recursion.

Here’s an example:

# Example is conceptual as Python's standard TreeNode class does not support threads.
# Assume we have a threaded binary tree and a method to get the next threaded node.

def inorder_traversal_threaded(root):
  while root and not root.is_threaded: 
    root = root.left
  while root: 
    print(root.value)
    root = root.get_next_threaded()

# Instead of providing code to modify TreeNode and its traversal, 
# we give a simple indication of how threaded traversal would conceptually look.

This example is conceptual, illustrating how an inorder traversal with a threaded binary tree might be performed.

Bonus One-Liner Method 5: Using Generators

A pythonic way to perform an inorder traversal is using generators with the yield construct, providing an elegant and concise solution.

Here’s an example:

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

def inorder_traversal_generator(root):
  if root:
    yield from inorder_traversal_generator(root.left)
    yield root.value
    yield from inorder_traversal_generator(root.right)

# Example tree
root = TreeNode(2)
root.left = TreeNode(1)
root.right = TreeNode(3)
print(list(inorder_traversal_generator(root)))

Output:

[1, 2, 3]

This Pythonic code uses a generator to yield node values in an inorder sequence, which can be collected into a list or iterated over directly.

Summary/Discussion

Method 1: Recursive Inorder Traversal. Simple and straightforward. It can lead to stack overflow on very deep trees.
Method 2: Iterative Inorder Traversal. More control over the process, avoids recursion stack limitations. It may be slightly more complex than the recursive approach.
Method 3: Morris Traversal. Memory-efficient as it doesn’t use stack or recursion. The tree is temporarily altered, which might not be acceptable in all cases.
Method 4: Threaded binary trees. They provide direct inorder traversal without additional memory. Requires the binary tree to be specially constructed as threaded.
Bonus Method 5: Generators. Compact and elegant. Utilizes Python’s yield syntax for lazy evaluation, useful for large trees.