Binary tree traversal is a fundamental operation in computer science, visiting each node in the tree in a specific order. This article covers four essential traversal methods with both recursive and iterative implementations.

Preorder Traversal (Root-Left-Right)

Preorder traversal visits the root node first, then the left subtree, followed by the right subtree.

Recursive Implementation

class Solution:
    def __init__(self):
        self.output = []
    
    def preorder_traversal(self, root):
        self._depth_first_search(root)
        return self.output
    
    def _depth_first_search(self, node):
        if node is None:
            return
        
        self.output.append(node.val)
        self._depth_first_search(node.left)
        self._depth_first_search(node.right)

Iterative Implementation

class Solution:
    def preorder_traversal(self, root):
        if root is None:
            return []
        
        output = []
        stack = [root]
        
        while stack:
            current = stack.pop()
            output.append(current.val)
            
            if current.right:
                stack.append(current.right)
            if current.left:
                stack.append(current.left)
        
        return output

The iterative version uses a stack to simulate the call stack behavior of recursion. The right child is pushed before the left child to ensure the left subtree is processed first.

Inorder Traversal (Left-Root-Right)

Inorder traversal visits the left subtree, then the root, and finally the right subtree. For binary search trees, this produces sorted order.

Recursive Implementation

class Solution:
    def __init__(self):
        self.output = []
    
    def inorder_traversal(self, root):
        self._process_subtree(root)
        return self.output
    
    def _process_subtree(self, node):
        if node is None:
            return
        
        self._process_subtree(node.left)
        self.output.append(node.val)
        self._process_subtree(node.right)

Iterative Implementation

class Solution:
    def inorder_traversal(self, root):
        output = []
        stack = []
        current = root
        
        while current or stack:
            while current:
                stack.append(current)
                current = current.left
            
            current = stack.pop()
            output.append(current.val)
            current = current.right
        
        return output

The iterative inorder traversal requires more thought. We traverse to the leftmost node, then process nodes as we backtrack, moving to right subtrees when possible.

Postorder Traversal (Left-Right-Root)

Postorder traversal visits both subtrees before the root node. This order is useful for deleting trees or evaluating expression trees.

Recursive Implementation

class Solution:
    def __init__(self):
        self.output = []
    
    def postorder_traversal(self, root):
        self._traverse(root)
        return self.output
    
    def _traverse(self, node):
        if node is None:
            return
        
        self._traverse(node.left)
        self._traverse(node.right)
        self.output.append(node.val)

Iterative Implementation

class Solution:
    def postorder_traversal(self, root):
        if root is None:
            return []
        
        output = []
        stack = []
        previous = None
        current = root
        
        while current or stack:
            while current:
                stack.append(current)
                current = current.left
            
            peek_node = stack[-1]
            
            if peek_node.right is None or peek_node.right == previous:
                output.append(peek_node.val)
                previous = peek_node
                stack.pop()
            else:
                current = peek_node.right
        
        return output

This iterative approach tracks the last visited node to determine whether we've finished processing the right subtree.

Level Order Traversal

Level order traversal visits nodes level by level from top to bottom, left to right. This requires a queue-based breadth-first search approach.

Implementation

class Solution:
    def level_order(self, root):
        if root is None:
            return []
        
        levels = []
        processing_queue = [root]
        
        while processing_queue:
            level_size = len(processing_queue)
            current_level = []
            
            for _ in range(level_size):
                node = processing_queue.pop(0)
                current_level.append(node.val)
                
                if node.left:
                    processing_queue.append(node.left)
                if node.right:
                    processing_queue.append(node.right)
            
            levels.append(current_level)
        
        return levels

Comparison of Traversal Methods

The recursive implementations are more intuitive and concise, while iterative versions demonstrate understanding of stack and queue data structures. Choosing between them depends on memory constraints and language-specific recurtion limits.