How to Traverse Binary Tree in Python: Simple Guide

To traverse a binary tree in Python, use preorder, inorder, or postorder traversal methods. These methods visit nodes in different orders by recursively visiting the root, left subtree, and right subtree in specific sequences.

Syntax

A binary tree traversal visits all nodes in a specific order. The common traversal methods are:

• Preorder: Visit root, then left subtree, then right subtree.
• Inorder: Visit left subtree, then root, then right subtree.
• Postorder: Visit left subtree, then right subtree, then root.

Each method is usually implemented as a recursive function that takes a node as input and processes it accordingly.

python

def preorder(node):
    if node:
        # Process node
        preorder(node.left)
        preorder(node.right)

def inorder(node):
    if node:
        inorder(node.left)
        # Process node
        inorder(node.right)

def postorder(node):
    if node:
        postorder(node.left)
        postorder(node.right)
        # Process node

Example

This example creates a simple binary tree and prints the nodes in preorder, inorder, and postorder traversal orders.

python

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

def preorder(node):
    if node:
        print(node.value, end=' ')
        preorder(node.left)
        preorder(node.right)

def inorder(node):
    if node:
        inorder(node.left)
        print(node.value, end=' ')
        inorder(node.right)

def postorder(node):
    if node:
        postorder(node.left)
        postorder(node.right)
        print(node.value, end=' ')

# Create tree:
#     1
#    / \
#   2   3
#  / \
# 4   5
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

print('Preorder traversal:')
preorder(root)
print('\nInorder traversal:')
inorder(root)
print('\nPostorder traversal:')
postorder(root)

Output

Preorder traversal:
1 2 4 5 3 
Inorder traversal:
4 2 5 1 3 
Postorder traversal:
4 5 2 3 1 

Common Pitfalls

Common mistakes when traversing binary trees include:

• Not checking if the node is None before accessing its children, causing errors.
• Mixing the order of recursive calls, which changes the traversal type.
• Forgetting to process the node at the correct time in the traversal sequence.

Always ensure the base case handles None nodes to stop recursion.

python

def wrong_inorder(node):
    # Missing base case check
    wrong_inorder(node.left)
    print(node.value, end=' ')
    wrong_inorder(node.right)

# Correct version

def correct_inorder(node):
    if node:
        correct_inorder(node.left)
        print(node.value, end=' ')
        correct_inorder(node.right)

Quick Reference

Traversal Type	Order of Visiting Nodes
Preorder	Root -> Left -> Right
Inorder	Left -> Root -> Right
Postorder	Left -> Right -> Root

Key Takeaways

Use recursion with base case checking for None nodes to traverse binary trees safely.

Preorder visits root before children; inorder visits root between children; postorder visits root after children.

Mixing the order of recursive calls changes the traversal type and output.

Always process the node at the correct step in the traversal sequence to get expected results.