import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
import java.util.Queue;

/** Runnable companion for the Atlas trees-and-traversals-in-java article. */
public final class TreeTraversalExamples {
    private TreeTraversalExamples() {}

    public static final class TreeNode {
        public final int value; // The value is data; it does not determine child positions.
        public TreeNode left;  // null means that this child does not exist.
        public TreeNode right;

        public TreeNode(int value) {
            this.value = value;
        }
    }

    public static List<Integer> inorderRecursive(TreeNode root) {
        List<Integer> order = new ArrayList<>(); // One result shared by the recursive calls.
        inorder(root, order);
        return order;
    }

    private static void inorder(TreeNode node, List<Integer> order) {
        if (node == null) return; // An empty subtree contributes no values.
        inorder(node.left, order); // Finish the entire left subtree, not just its leftmost node.
        order.add(node.value); // IN: record this node between its two subtrees.
        inorder(node.right, order); // Finish the entire right subtree before returning.
    }

    public static List<Integer> preorderRecursive(TreeNode root) {
        List<Integer> order = new ArrayList<>();
        preorder(root, order);
        return order;
    }

    private static void preorder(TreeNode node, List<Integer> order) {
        if (node == null) return; // There is no node to record or explore.
        order.add(node.value); // PRE: record this node before exploring its children.
        preorder(node.left, order); // Complete the left subtree first.
        preorder(node.right, order); // Then complete the right subtree.
    }

    public static List<Integer> postorderRecursive(TreeNode root) {
        List<Integer> order = new ArrayList<>();
        postorder(root, order);
        return order;
    }

    private static void postorder(TreeNode node, List<Integer> order) {
        if (node == null) return; // The empty subtree is already finished.
        postorder(node.left, order); // Finish the left child and all its descendants.
        postorder(node.right, order); // Finish the right child and all its descendants.
        order.add(node.value); // POST: record this node only after both sides finish.
    }

    public static List<Integer> inorderIterative(TreeNode root) {
        List<Integer> order = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>(); // Ancestors waiting for their inorder turn.
        TreeNode current = root;

        while (current != null || !stack.isEmpty()) { // Stop only when no subtree or ancestor remains.
            while (current != null) {
                stack.push(current); // Save where to return after this left subtree.
                current = current.left; // Keep moving left before recording a value.
            }
            TreeNode node = stack.pop(); // Its left subtree is now finished.
            order.add(node.value); // Record the current subtree root in the middle.
            current = node.right; // Explore this right subtree before the next waiting ancestor.
        }
        return order; // A null root naturally produces an empty list.
    }

    public static List<Integer> preorderIterative(TreeNode root) {
        List<Integer> order = new ArrayList<>();
        if (root == null) return order; // ArrayDeque must not receive a null element.
        Deque<TreeNode> stack = new ArrayDeque<>(); // Subtree roots that still need processing.
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop(); // Choose the most recently scheduled subtree.
            order.add(node.value); // PRE: record its root immediately.
            if (node.right != null) stack.push(node.right); // Push right first: it must wait below left.
            if (node.left != null) stack.push(node.left); // Left is on top, so it is processed next.
        }
        return order;
    }

    public static List<Integer> postorderIterative(TreeNode root) {
        List<Integer> order = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>(); // Nodes whose subtrees are not both finished yet.
        TreeNode current = root;
        TreeNode lastVisited = null; // The exact node most recently recorded, not just its value.

        while (current != null || !stack.isEmpty()) {
            if (current != null) {
                stack.push(current); // Remember this node, but do not record it yet.
                current = current.left; // Finish its left subtree first.
            } else {
                TreeNode node = stack.peek(); // Inspect the waiting node without removing it.
                if (node.right != null && lastVisited != node.right) {
                    current = node.right; // Its right subtree exists and has not finished.
                } else {
                    order.add(node.value); // Both subtrees are finished, so POST may record this node.
                    lastVisited = stack.pop(); // Tell the waiting parent which child just finished.
                }
            }
        }
        return order;
    }

    public static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> levels = new ArrayList<>();
        if (root == null) return levels; // An empty tree has no levels to return.
        Queue<TreeNode> queue = new ArrayDeque<>(); // FIFO keeps shallower nodes ahead of deeper ones.
        queue.offer(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size(); // Freeze this count BEFORE adding the next level's children.
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < levelSize; i++) { // Remove exactly the nodes in the current level.
                TreeNode node = queue.poll(); // Process the oldest waiting node.
                level.add(node.value);
                if (node.left != null) queue.offer(node.left); // Keep left-to-right order within a level.
                if (node.right != null) queue.offer(node.right);
            }
            levels.add(level); // Keep level boundaries, rather than returning one flat sequence.
        }
        return levels;
    }

    public static List<List<Integer>> levelOrderRecursive(TreeNode root) {
        List<List<Integer>> levels = new ArrayList<>();
        if (root == null) return levels;
        Queue<TreeNode> queue = new ArrayDeque<>(); // The queue still determines BFS order.
        queue.offer(root);
        collectNextLevel(queue, levels);
        return levels;
    }

    private static void collectNextLevel(Queue<TreeNode> queue, List<List<Integer>> levels) {
        if (queue.isEmpty()) return; // No next level remains: stop the recursion.
        int levelSize = queue.size(); // Each call handles exactly one complete level.
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            level.add(node.value);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        levels.add(level);
        collectNextLevel(queue, levels); // The call stack grows once per level; Java does not erase it.
    }

    /** Fifteen nodes: a perfect tree which also happens to be a binary search tree. */
    public static TreeNode exampleA() {
        TreeNode[] nodes = new TreeNode[16];
        for (int value = 1; value <= 15; value++) nodes[value] = new TreeNode(value);
        nodes[8].left = nodes[4]; nodes[8].right = nodes[12];
        nodes[4].left = nodes[2]; nodes[4].right = nodes[6];
        nodes[12].left = nodes[10]; nodes[12].right = nodes[14];
        nodes[2].left = nodes[1]; nodes[2].right = nodes[3];
        nodes[6].left = nodes[5]; nodes[6].right = nodes[7];
        nodes[10].left = nodes[9]; nodes[10].right = nodes[11];
        nodes[14].left = nodes[13]; nodes[14].right = nodes[15];
        return nodes[8];
    }

    /** Thirteen nodes: missing left children at 40 and 60; NOT a binary search tree. */
    public static TreeNode exampleB() {
        TreeNode[] nodes = new TreeNode[14];
        for (int i = 1; i <= 13; i++) nodes[i] = new TreeNode(i * 10);
        nodes[1].left = nodes[2]; nodes[1].right = nodes[3];
        nodes[2].left = nodes[4]; nodes[2].right = nodes[5];
        nodes[3].left = nodes[6]; nodes[3].right = nodes[7];
        nodes[4].right = nodes[8];
        nodes[5].left = nodes[9]; nodes[5].right = nodes[10];
        nodes[6].right = nodes[11];
        nodes[7].left = nodes[12]; nodes[7].right = nodes[13];
        return nodes[1];
    }

    public static void main(String[] args) {
        TreeNode a = exampleA(); // Builds the exact fifteen-node Tree A shown in the article.
        TreeNode b = exampleB(); // Builds the exact thirteen-node Tree B, including its missing children.
        for (TreeNode root : List.of(a, b)) {
            System.out.println("Inorder recursive: " + inorderRecursive(root));
            System.out.println("Inorder iterative: " + inorderIterative(root));
            System.out.println("Preorder recursive: " + preorderRecursive(root));
            System.out.println("Preorder iterative: " + preorderIterative(root));
            System.out.println("Postorder recursive: " + postorderRecursive(root));
            System.out.println("Postorder iterative: " + postorderIterative(root));
            System.out.println("BFS levels: " + levelOrder(root));
            System.out.println("Recursive BFS levels: " + levelOrderRecursive(root));
        }
    }
}
