Algorithms { public static void traverseByDepth(Node root, NodeVisitor visitor){ Deque<Pair<Node, Integer>> nodeAndNests = new LinkedList<Pair<Node, Integer>>(); nodeAndNests.offer(Pair.create(root, 0)); Pair<Node, Integer> nodeAndNest = null; while((nodeAndNest = nodeAndNests.poll()) != null){ Node node = nodeAndNest.getFirst(); int nest = nodeAndNest.getSecond(); if(!visitor.visit(node, nest)) return; nest++; Node[] children = node.getChildren(); int n = children.length; for(int i = n - 1; i >= 0; i--){ nodeAndNests.offerFirst(Pair.create(children[i], nest)); } } }  static void traverseByBreadth(Node root, NodeVisitor visitor); static void traverseByDepth(Node root, NodeVisitor visitor); static void dump(Node root, Writer writer); static boolean contains(Node root, String text); Iterable<String> commonPrefixSearch(Node root, String query);  }
@Test public void test_traverseByDepth(){ final StringBuilder letters = new StringBuilder(); final StringBuilder nests = new StringBuilder(); Algorithms.traverseByDepth(root, new NodeVisitor() { @Override public boolean visit(Node node, int nest) { letters.append(node.getLetters()); nests.append(nest); return true; } }); Assert.assertEquals("abefhcdg", letters.toString()); Assert.assertEquals("01223112", nests.toString()); }