Implementing depth-first traversals using recursive programming requires three key components:

1. Function parameters and return value definition
2. Termination condition handling
3. Single-layer recurison logic implementation

Implementation Examples

// Pre-order traversal
class RecursiveTraversal {
    public List<integer> traversePreOrder(TreeNode root) {
        List<integer> output = new ArrayList<>();
        processNode(root, output);
        return output;
    }

    private void processNode(TreeNode node, List<integer> list) {
        if (node == null) return;
        list.add(node.val);
        processNode(node.left, list);
        processNode(node.right, list);
    }
}
</integer></integer></integer>

// In-order traversal
class RecursiveTraversal {
    public List<integer> traverseInOrder(TreeNode root) {
        List<integer> result = new ArrayList<>();
        traverseLeft(root, result);
        return result;
    }

    private void traverseLeft(TreeNode node, List<integer> list) {
        if (node == null) return;
        traverseLeft(node.left, list);
        list.add(node.val);
        traverseLeft(node.right, list);
    }
}
</integer></integer></integer>

Iterative Traversal

Stack-based implementasions for traversal without recursion:

Pre-order Implementation

class IterativeTraversal {
    public List<integer> preOrderTraversal(TreeNode root) {
        List<integer> result = new ArrayList<>();
        if (root == null) return result;
        
        Stack<treenode> nodeStack = new Stack<>();
        nodeStack.push(root);
        
        while (!nodeStack.isEmpty()) {
            TreeNode current = nodeStack.pop();
            result.add(current.val);
            
            if (current.right != null) {
                nodeStack.push(current.right);
            }
            if (current.left != null) {
                nodeStack.push(current.left);
            }
        }
        return result;
    }
}
</treenode></integer></integer>

Post-order Variation

Modified pre-order followed by result reversal:

class IterativeTraversal {
    public List<integer> postOrderTraversal(TreeNode root) {
        List<integer> result = new ArrayList<>();
        if (root == null) return result;
        
        Stack<treenode> nodeStack = new Stack<>();
        nodeStack.push(root);
        
        while (!nodeStack.isEmpty()) {
            TreeNode current = nodeStack.pop();
            result.add(current.val);
            
            if (current.left != null) {
                nodeStack.push(current.left);
            }
            if (current.right != null) {
                nodeStack.push(current.right);
            }
        }
        Collections.reverse(result);
        return result;
    }
}
</treenode></integer></integer>

Unified Iteration Framework

Standardized approach using marker objects for all traversal types:

In-order Implementation

class UnifiedTraversal {
    public List<integer> inOrderTraversal(TreeNode root) {
        List<integer> output = new ArrayList<>();
        Stack<treenode> stack = new Stack<>();
        
        if (root != null) stack.push(root);
        
        while (!stack.isEmpty()) {
            TreeNode current = stack.peek();
            
            if (current != null) {
                stack.pop();
                if (current.right != null) stack.push(current.right);
                stack.push(current);
                stack.push(null);
                if (current.left != null) stack.push(current.left);
            } else {
                stack.pop();
                current = stack.pop();
                output.add(current.val);
            }
        }
        return output;
    }
}
</treenode></integer></integer>

Level-order Traversal

Breadth-first approach using queue-based processing:

Iterative Implemantation

class LevelOrderTraversal {
    public List<list>> traverseByLevel(TreeNode root) {
        List<list>> result = new ArrayList<>();
        if (root == null) return result;
        
        Queue<treenode> queue = new LinkedList<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            List<integer> currentLevel = new ArrayList<>();
            int levelSize = queue.size();
            
            for (int i = 0; i < levelSize; i++) {
                TreeNode current = queue.poll();
                currentLevel.add(current.val);
                
                if (current.left != null) {
                    queue.offer(current.left);
                }
                if (current.right != null) {
                    queue.offer(current.right);
                }
            }
            result.add(currentLevel);
        }
        return result;
    }
}
</integer></treenode></list></list>