How print a Binary Tree from a Queue?
This algorithm will allow to print a text input “[n1, n2, n3, …, nn]” in the form of a binary tree.
This time we’re going to use a very interesting data structure known as Queue, its way of manages traffic is F.I.F.O (First In First On), in contradiction to the Stack, that manages traffic as L.I.F.O (Last In Last Out).
The main method, the first thing it does, is to read from a buffer the line that the user types and constantly listens in case the user wants to continue executing more lines of the type “[n1, n2, n3, …, nn]”:
Inside the while loop we create the instance of the TreeNode object that has the following structure:
In the instance that we called “root” let’s put the result of the stringToTreeNode() method, which it does is the string entered by the user, sort it according to the structure that a binary tree has …
Let’s see how from a string in the form of an array we can order it according to the structure of a binary tree (children, siblings, parents, grandparents, etc).
The method in code looks like this:
A little bit robust, but it is what it is! :)
The first thing we do to the string input = “[n1, n2, n3, …, nn]” is to do a .strim() to eliminate the white spaces that the string may have at the beginning and at the end, too, with the .substring() method we remove the brackets “[]” and then we are left with only input = “n1, n2, n3, …, nn”.
We must do the validation if the length of the string is equal to 0, that means that nothing else needs to be evaluated and we return null because the string is empty.
We create an array that we will call parts where we put the string with the .split() method, which what will do is that each element that separates it “,” will be put in a space of the array.
As we already know that the array has at least one element, then, we put the first parts[0] element in a variable called item that will be the root of our tree.
Now, we are going to create a Queue of type TreeNode (A queue where its content will be objects of type TreeNode) and when instantiating it of type LinkedList we will have the .add() method to add said root (parts[0]).
Now, the interesting work takes place in the while loop that I’m going to explain next.
This is a loop that will be iterated as long as there are elements in the nodeQueue queue.
We create another instance of the TreeNode object where we put the value obtained when we apply the .remove() method to the Queue
The validation of looking if the value of index is equal to the length of the array is to avoid making unnecessary calculations, in case it is fulfilled we break the cycle with break.
Now, in item we are going to put the value found in parts [index++], remember that index was initialized at 1, with the iterations of the while it will be adding one unit to this value.
We validate that item has a value other than null so that, In the left property that has the node object instantiated by TreeNode put the value that item has in that iteration.
We validate again to make sure there are still items to order.
The next element will be the one belonging to the right branch.
In short, an iteration of the loop sorts root — left — right.
After consuming (ordering) all the elements in the array, I return root, which is an object that has the property left and right, in turn, each node (left or right) also has children (left and right).
Well, now what is the really important of having an object that has another object inside and another and another inside … we are going to represent it “more beautiful” so that the user can get an idea of what a binary tree is, for that we have the prettyPrintTree() method that receives 3 important parameters.
1. node = It is the TreeNode object ordered as it will be seen in the tree.
2. prefix = String to format the tree.
3. isLeft = Boolean value to know towards which lake the tree divides.
The method look like this:
We must keep in mind that this method is recursive (it must be, otherwise it would be chaotic to print it).
The first thing we do to validate if the node is null, and if this statement is true then immediately return “Empty tree” and no further calculations are needed.
we are going to evaluate the right node of the root and in composing the structure playing with the number of nodes that are to the right and left. Calling the function again it is possible to concatenate the current structure of the tree with the previous structure, resulting in something like this.
You can check all the code on my repository :)
