Tree Traversal — DFS and BFS

import java.util.*;
import java.util.function.Consumer;

public class TreeTraversal {

    static class TreeNode<T> {
        T value;
        TreeNode<T> left, right;

        TreeNode(T value) { this.value = value; }
        TreeNode(T value, TreeNode<T> left, TreeNode<T> right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    // DFS — Pre-order (root, left, right)
    static <T> void preOrder(TreeNode<T> node, Consumer<T> visit) {
        if (node == null) return;
        visit.accept(node.value);
        preOrder(node.left, visit);
        preOrder(node.right, visit);
    }

    // DFS — In-order (left, root, right) → sorted for BST
    static <T> void inOrder(TreeNode<T> node, Consumer<T> visit) {
        if (node == null) return;
        inOrder(node.left, visit);
        visit.accept(node.value);
        inOrder(node.right, visit);
    }

    // DFS — Post-order (left, right, root)
    static <T> void postOrder(TreeNode<T> node, Consumer<T> visit) {
        if (node == null) return;
        postOrder(node.left, visit);
        postOrder(node.right, visit);
        visit.accept(node.value);
    }

    // BFS — Level-order
    static <T> List<List<T>> levelOrder(TreeNode<T> root) {
        List<List<T>> levels = new ArrayList<>();
        if (root == null) return levels;

        Queue<TreeNode<T>> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            int size = queue.size();
            List<T> level = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode<T> node = queue.poll();
                level.add(node.value);
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
            levels.add(level);
        }
        return levels;
    }

    // Iterative in-order using stack
    static <T> List<T> inOrderIterative(TreeNode<T> root) {
        List<T> result = new ArrayList<>();
        Deque<TreeNode<T>> stack = new ArrayDeque<>();
        TreeNode<T> current = root;

        while (current != null || !stack.isEmpty()) {
            while (current != null) {
                stack.push(current);
                current = current.left;
            }
            current = stack.pop();
            result.add(current.value);
            current = current.right;
        }
        return result;
    }

    // Tree height
    static <T> int height(TreeNode<T> node) {
        if (node == null) return 0;
        return 1 + Math.max(height(node.left), height(node.right));
    }

    public static void main(String[] args) {
        //       4
        //      / \
        //     2   6
        //    / \ / \
        //   1  3 5  7
        var tree = new TreeNode<>(4,
            new TreeNode<>(2, new TreeNode<>(1), new TreeNode<>(3)),
            new TreeNode<>(6, new TreeNode<>(5), new TreeNode<>(7))
        );

        System.out.print("Pre:  "); preOrder(tree, v -> System.out.print(v + " "));
        System.out.print("\nIn:   "); inOrder(tree, v -> System.out.print(v + " "));
        System.out.print("\nPost: "); postOrder(tree, v -> System.out.print(v + " "));
        System.out.println("\nBFS: " + levelOrder(tree));
        System.out.println("Height: " + height(tree));
    }
}