Binary Tree Node Definition

public class BinNode {
    int data;
    BinNode leftChild;
    BinNode rightChild;

    BinNode() {}

    BinNode(int data) {
        this.data = data;
    }

    BinNode(int data, BinNode leftChild, BinNode rightChild) {
        this.data = data;
        this.leftChild = leftChild;
        this.rightChild = rightChild;
    }
}

Recursive Traversal Strategies

When implementing recursive depth-first searches, three key aspects must be clearly defined:

• The method's input parameters and return type.
• The termination condition (base case).
• The primary porcessing logic and where the recursive calls are positioned relative to the processing step.

Pre-order Traversal

Process the current node, then recursively traverse the left subtree, followed by the right subtree.

class Solution {
    public List<Integer> traversePreorder(BinNode root) {
        List<Integer> path = new ArrayList<>();
        buildPreorder(root, path);
        return path;
    }

    private void buildPreorder(BinNode node, List<Integer> path) {
        if (node == null) return;
        path.add(node.data);
        buildPreorder(node.leftChild, path);
        buildPreorder(node.rightChild, path);
    }
}

In-order Traversal

Recursively traverse the left subtree, process the current node, and then traverse the right subtree.

class Solution {
    public List<Integer> traverseInorder(BinNode root) {
        List<Integer> path = new ArrayList<>();
        buildInorder(root, path);
        return path;
    }

    private void buildInorder(BinNode node, List<Integer> path) {
        if (node == null) return;
        buildInorder(node.leftChild, path);
        path.add(node.data);
        buildInorder(node.rightChild, path);
    }
}

Post-order Traversal

Recursively traverse the left subtree, then the right subtree, and process the current node last.

class Solution {
    public List<Integer> traversePostorder(BinNode root) {
        List<Integer> path = new ArrayList<>();
        buildPostorder(root, path);
        return path;
    }

    private void buildPostorder(BinNode node, List<Integer> path) {
        if (node == null) return;
        buildPostorder(node.leftChild, path);
        buildPostorder(node.rightChild, path);
        path.add(node.data);
    }
}

Level-order Traversal (Recursive)

By passing the current depth as a paramter, we can map each node to its corresponding level in the result list.

class Solution {
    public List<List<Integer>> traverseLevelOrder(BinNode root) {
        List<List<Integer>> levels = new ArrayList<>();
        processLevel(root, 0, levels);
        return levels;
    }

    private void processLevel(BinNode node, int depth, List<List<Integer>> levels) {
        if (node == null) return;
        if (levels.size() == depth) {
            levels.add(new ArrayList<>());
        }
        levels.get(depth).add(node.data);
        processLevel(node.leftChild, depth + 1, levels);
        processLevel(node.rightChild, depth + 1, levels);
    }
}

Iterative Traverasl with Unified Stack Template

To standardize iterative traversals, we can use a marker-based stack approach. By pushing a null marker after a node, we indicate that the node should be processed (added to the result) when the marker is encountered again. The order of pushing children determines the traversal type.

Pre-order Iterative

Push right, then left, then the node itself followed by a null marker.

class Solution {
    public List<Integer> iterPreorder(BinNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        Deque<BinNode> stack = new ArrayDeque<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            BinNode current = stack.pop();
            if (current != null) {
                if (current.rightChild != null) stack.push(current.rightChild);
                if (current.leftChild != null) stack.push(current.leftChild);
                stack.push(current);
                stack.push(null);
            } else {
                BinNode actual = stack.pop();
                result.add(actual.data);
            }
        }
        return result;
    }
}

In-order Iterative

Push right, then the node with a null marker, and finally the left child.

class Solution {
    public List<Integer> iterInorder(BinNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        Deque<BinNode> stack = new ArrayDeque<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            BinNode current = stack.pop();
            if (current != null) {
                if (current.rightChild != null) stack.push(current.rightChild);
                stack.push(current);
                stack.push(null);
                if (current.leftChild != null) stack.push(current.leftChild);
            } else {
                BinNode actual = stack.pop();
                result.add(actual.data);
            }
        }
        return result;
    }
}

Post-order Iterative

Push the node with a null marker first, then the right child, and finally the left child.

class Solution {
    public List<Integer> iterPostorder(BinNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        Deque<BinNode> stack = new ArrayDeque<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            BinNode current = stack.pop();
            if (current != null) {
                stack.push(current);
                stack.push(null);
                if (current.rightChild != null) stack.push(current.rightChild);
                if (current.leftChild != null) stack.push(current.leftChild);
            } else {
                BinNode actual = stack.pop();
                result.add(actual.data);
            }
        }
        return result;
    }
}

Level-order Traversal (Iterative BFS)

Utilize a queue to process nodes level by level, tracking the number of nodes at each depth to form inner lists.

class Solution {
    public List<List<Integer>> iterLevelOrder(BinNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        Queue<BinNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> currentLevel = new ArrayList<>(levelSize);
            for (int i = 0; i < levelSize; i++) {
                BinNode node = queue.poll();
                currentLevel.add(node.data);
                if (node.leftChild != null) queue.offer(node.leftChild);
                if (node.rightChild != null) queue.offer(node.rightChild);
            }
            result.add(currentLevel);
        }
        return result;
    }
}