Yesterday my wife had an appointment at the hair salon. The gal that cut her hair commented that there were more people than usual complaining of seasonal allergies; some of them have never before experienced symptoms. My wife and I have some light allergies every season. Some days this year we have experienced strong symptoms. Hopefully things will get better soon.
Last evening in the local news, it was mentioned that due to the amount of water due to rain and melted snow, farmers are a couple weeks behind planting their crops. Having grains and vegetables is more important than experiencing allergy symptoms. Hopefully all will turn out well as the season progresses. The forecast for today calls for strong rain starting around mid morning and ending early tomorrow. Most of the rivers in this area are at or above normal flood levels. Hope the forecast falls short in moisture.
This week I had the opportunity to talk with a fellow software developer. We briefly discussed the approach of traversing a data structure using loops and recursion. It seems that if the number of objects is relatively small, recursion is elegant approach. That said, for large number of objects, recursion may fail due to execution stack limitations.
The idea is to traverse a data structure representing a Person. The person may or may not have a father and a mother. The goal is to return and display a list of names starting with the specified person. At the time no order for the names was discussed. As we look at the code you will cover some ideas that we could use to get the names in different orders.
Let’s first look at the Person class:
package family.names.canessa;
import java.util.ArrayList;
import java.util.List;
/*
*
*/
public class Person {
// **** members ****
String name;
Person mother;
Person father;
List<String> names = null;
// **** constructor ****
public Person(String name, Person mother, Person father) {
this.name = name;
this.mother = mother;
this.father = father;
}
// **** constructor ****
public Person() {
this.names = new ArrayList<String>();
}
// **** traversal ****
// public void traversal(Person p, List<String> names) {
public void traversal(Person p) {
// **** terminate recursion ****
if (p == null)
return;
// ???? display node ????
System.out.println("traversal <<< p.name ==>" + p.name + "<==");
// **** visit left node (e.g., mother) ****
// traversal(p.mother, names);
traversal(p.mother);
// **** save name ****
names.add(p.name);
// **** visit right node (e.g., father) ****
// traversal(p.father, names);
traversal(p.father);
}
// **** get list of names ****
public List<String> getNames() {
return this.names;
}
}
In the members we have the three required members. Depending on what I was experimenting with, I added a list of names. As we will see, we could have done altogether without a list and just display the names as we encounter them.
We have two constructors. The first constructor is used in the first approach, while the second constructor is used in the second one. I commented out the declaration of the traversal method used when passing the list of names. On the not commented one I decided to use a class member.
As I am going through the explanation, I feel that I should have separated the different passes with entire methods instead of commenting out lines. Sorry about that. I will keep this in mind for future posts.
Now let’s take a look of the console output for the first approach using as starters the 3 different persons in the solution:
<<< starting name: Fred Fred Edna Ed <<< starting name: Wilma Wilma Pearl <<< starting name: Pebbles Pebbles Wilma Pearl Fred Edna Ed
As we run with different people we get different results. The one that has the highest coverage is Pebbles.
Now let’s take a look at the solution:
package family.names.canessa;
import java.util.ArrayList;
import java.util.List;
/*
*
*/
public class Solution {
// **** get the names for a person ****
static void getNames(Person p, List<String> names) {
// **** termination condition ****
if (p == null)
return;
// **** add the name of this person ****
names.add(p.name);
// **** check the mother branch ****
getNames(p.mother, names);
// **** check the father branch ****
getNames(p.father, names);
}
// **** get all names starting with this person ****
static List<String> getAllNames(Person p) {
// **** ****
ArrayList<String> names = new ArrayList<String>();
// **** display name for starting person ****
System.out.println("<<< starting name: " + p.name);
// **** get all names starting here (recursive call) ****
getNames(p, names);
// **** ****
return names;
}
/*
* Test scaffold
*/
public static void main(String[] args) {
// **** small family ****
Person fred = new Person( "Fred",
new Person("Edna", null, null),
new Person("Ed", null, null));
Person wilma = new Person( "Wilma",
new Person("Pearl", null, null),
null);
Person pebbles = new Person("Pebbles",
wilma,
fred);
// **** get all names starting with this person ****
// List<String> names = getAllNames(fred);
// List<String> names = getAllNames(wilma);
// List<String> names = getAllNames(pebbles);
Person p = new Person();
p.traversal(pebbles); // fred, wilma or pebbles
List<String> names = p.getNames();
// **** display the name(s) ****
for (String name : names) {
System.out.println(name);
}
}
}
Let’s look at the main() method. We declare 3 persons and populate the objects with their name and objects for their parents. In some cases we leave them blank (null).
The first approach uses the getAllNames() method. We pass the starting person and we need to return a list of names. The code for this method is in the same source file. Since we are using recursion, we declare a list, display the name of the starting person (this is done only for convenience) and then we call a recursive method to traverse the person object collecting all the names.
The getName() method is used to get a name at a time. We first decide when recursion stops. If not, we add the name to the list and then continue with the mother object. When that returns, we repeat the process with the father object.
The list of names is then displayed by the main() method. This is a simple 
recursive approach. If you stop and look at it, it should remind you of a Binary Search Tree (BST) traversal. That approach is implemented in the Person class. When you traverse a BST you can do it in 3 different ways: in order, pre order and post order. They all differ when the name of the node (person) is displayed. The traversal() method is used to recursively traverse the person structures from the starting one. Recursion is ended when we reach a null person. The names are stored between traversals of the mother and father which represent an in order traversal.
When the traversal is completed, we get the list of names and display it.
traversal <<< p.name ==>Pebbles<== traversal <<< p.name ==>Wilma<== traversal <<< p.name ==>Pearl<== traversal <<< p.name ==>Fred<== traversal <<< p.name ==>Edna<== traversal <<< p.name ==>Ed<== Pearl Wilma Pebbles Edna Fred Ed traversal <<< p.name ==>Wilma<== traversal <<< p.name ==>Pearl<== Pearl Wilma traversal <<< p.name ==>Fred<== traversal <<< p.name ==>Edna<== traversal <<< p.name ==>Ed<== Edna Fred Ed
This is simple but seemed to me like a good exercise in recursion. As usual there are different ways to skin a cat, but based on requirements typically one is best. In this case any approach seems to be fine.
As usual I will be putting all the code in my GitHub repository.
If you have comments or questions regarding this or any other post in this blog, or if you would like me to help with any phase in the SDLC (Software Development Life Cycle) of a product or service, please do not hesitate and leave me a note below. Requests for help will remain private.
Keep on reading and experimenting. It is the best way to learn!
John
Follow me on Twitter: @john_canessa