Some weeks ago, in the social networks, I scrolled over some comments and posts about a somewhat simple challenge: how to traverse a tree, in a way to print each level of it in a new line?
Let's say, we have some tree, like:
This is a classical binary tree with three levels. Accordingly with the challenge, we have to print this tree in the following way:
1
2 3
4 5 6 7
Fundamentals of Graph Traversal
Graphs? WTF?????
Wait there!
The graph is a fundamental data structure in the sense that the majority of data structures derivates from it. Graphs are structured in a way where nodes are interconected with anothers in randomic ways, and each node can be connected with another one.
Graphs can be directed or not. Directed graphs have nodes, not only connected between it, but each connection have a direction. In the graph above, the Node 1 can traverse to node 2 and 3, but Node 2 cannot traverse to Node 1, only to the Node 4. When graph is undirected, the traversal can go back and forth.
The traversal in graphs can happen in two ways: Breadth First Traversal (BFS) and Depth First Traversal (DFS).
Breadth First Traversal
Breadth First Traversal is made in a fashion where we go to each of level of traversal equally in the graph, before advancing another level.
Let's remember the former image graph. First, we start in the node 1, then we go and visit nodes 2, 3, 5 and 6, and then, finally, visit nodes 4 and 7.
When we traversal graphs, normally we can use auxiliary data structures. Let's define a graph node as following:
public class Node<T> {
public final T value;
public final Collection<Node<T>> children;
public Node(T value, Collection<Node<T>> children) {
this.value = value;
this.children = children;
}
}
The auxiliary data structure for breadth first traversal is the queue. Each time we visit a node, we gonna put the children at the end of queue, and while advancing in the queue, the levels of traversal are well defined, and we gonna advance each level at a time:
public class BFS {
public void traverse(Node<?> node) {
Queue<Node<?>> q = new LinkedList<>();
q.add(node);
while (!q.isEmpty()) {
var n = q.remove();
System.out.println(n.value);
q.addAll(n.children);
}
}
}
Let's take this graph:
Node<String> graph = new Node<>(
"1",
List.of(
new Node<>("2",
List.of(new Node<>("5", Collections.emptyList()),
new Node<>("6", Collections.emptyList()))),
new Node<>("3",
List.of(new Node<>("7", Collections.emptyList()),
new Node<>("8", Collections.emptyList()))),
new Node<>("4", Collections.emptyList())));
When traversed in BFS fashion, we get:
1
2
3
4
5
6
7
8
Depth First Traversal
If in BFS we visit near nodes first, in Depth First Traversal we advance the most possible deep level in one direction before going to other direction.
Let's take the same graph from the first image. If we traverse it in a DFS fashion, we gonna start at the node 1, then go into the direction of 2 and then 4. Next, we visit 3 and 7. Then 6 and then 5:
If we go in only one direction, we use the Stack as auxiliary data structure, because the inputs and outputs of this structure occurs in only one channel.
If we use stack, we can use the call stack too, making recursive traversals in the graph.
Let's implement it using first a regular stack:
public class DFSStack {
public void traverse(Node<?> node) {
var stack = new Stack<Node<?>>();
stack.push(node);
while (!stack.isEmpty()) {
var n = stack.pop();
System.out.println(n.value);
stack.addAll(n.children);
}
}
}
And when testing, we get this:
1
4
3
8
7
2
6
5
And then, using a recursive approach:
public class DFSRecursive {
public void traverse(Node<?> node) {
System.out.println(node.value);
for (var n : node.children) {
traverse(n);
}
}
}
And testing this, we get:
1
2
5
6
3
7
8
4
Using graph fundamentals to solve the challenge
With this knowledge, we know that:
- The tree is only a configuration of graph
- Graphs can be traversed in two ways: BFS and DFS
- Therefore, trees can be traversed in that ways
If we can use these traversals in tree, we need only a type of traversal that can, therefore, differentiate between levels, and I think the BFS is perfect for this.
But how can we differentiate between one level of the tree and another?
It's easy: we can put a dummy node, with a null value inside it, that makes this difference for us. This dummy node will indicate that we are at the end of the actual level, and then we can move this dummy node to the end of the queue, to mark each end of level.
Let's implement this:
public class PrintTree {
public void traverse(Node<?> node) {
Queue<Node<?>> queue = new LinkedList<Node<?>>();
var dummy = new Node<Object>(null, Collections.emptyList());
queue.add(node);
queue.add(dummy);
while (!queue.isEmpty()) {
var n = queue.remove();
if (n.value == null) {
System.out.printf("\n");
queue.add(dummy);
} else {
System.out.print(n.value + " ");
}
queue.addAll(n.children);
}
}
}
A simple implementation at first, but we have a problem in this implementation.
When we test it, we get the following behavior:
<=<===========--> 87% EXECUTING [16s]
> :lib:test > 0 tests completed
> :lib:test > Executing test com.eronalves.printtreelevels.TestPrint
The test execution gets stalled, only appending new line chars to the console.
Of course, our implementation has no stop condition, and get's appending a new dummy node each time it gets a dummy node from the queue, that way, appending new lines to the console for ever.
How can we stop the execution in a correct way?
Simple: we gonna verify if the queue is empty when appending the dummy node. If it's empty, then the graph is over. Otherwise, the queue have graph nodes yet, so we continue to append dummy nodes at the end:
if (!queue.isEmpty()) {
queue.add(dummy);
}
And now with test, we finally get:
1
2 3 4
5 6 7 8
Top comments (0)