Imperative Tree Traversal | BFS, DFS

Traversal.java

package org.example.structures.tree;

import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.function.Consumer;

public class Traversal {
    public static class Node {

        public final char value;
        public final List<Node> children = new LinkedList<>();

        public Node(char value, Node... children) {
            this.value = value;
            if (children != null) {
                this.children.addAll(Arrays.asList(children));
            }
        }

        @Override
        public String toString() {
            if (children.isEmpty()) {
                return "[%c]".formatted(value);
            } else {
                return "(%c)".formatted(value);
            }
        }
    }

    public static List<Node> bfs(Node root) {
        var frontier = new LinkedList<>(root.children);
        var visited = new HashSet<>(List.of(root));
        var seq = new LinkedList<>(List.of(root));

        while (!frontier.isEmpty()) {
            var head = frontier.pollFirst();
            seq.add(head);
            visited.add(head);
            frontier.addAll(head.children);
        }

        return seq;
    }

    public static List<Node> dfs(Node root, Consumer<List<Node>> fullSequenceVisitor) {
        var path = new LinkedList<>(List.of(root));
        var visited = new HashSet<Node>();
        var seq = new LinkedList<Node>();

        while (!path.isEmpty()) {
            var tail = path.getLast();

            var unseenChild = tail.children.stream()
                    .filter(child -> !visited.contains(child))
                    .findFirst().orElse(null);

            if (unseenChild == null) {
                visited.add(tail);
                if (tail.children.isEmpty()) {
                    fullSequenceVisitor.accept(new LinkedList<>(path));
                }
                seq.add(path.removeLast()); // == tail
            } else {
                path.add(unseenChild);
            }
        }
        return seq;
    }

    public static void main(String[] args) {
        var sequencePrinter = new Consumer<List<Node>>() {

            @Override
            public void accept(List<Node> nodes) {
                var seq = nodes.stream()
                        .map(n -> n.value)
                        .reduce("", (str, c) -> str + c, (s1, s2) -> s1 + s2);
                System.out.println("=> " + seq);
            }
        };

        var tree = new Node('3',
                new Node('2', new Node('1')),
                new Node('5',
                        new Node('4'),
                        new Node('7', new Node('6'))));

        System.out.println(bfs(tree));
        System.out.println(dfs(tree, sequencePrinter));

        var t2 = new Node('A',
                new Node('B', new Node('D'), new Node('E')), new Node('C'));
        System.out.println(bfs(t2));
        System.out.println(dfs(t2, sequencePrinter));
    }

}