Algorithms: Searching an Unbalanced Tree

(image source)

I worked through a recent code challenge and wanted to write about it. The challenge was to evaluate a tree and identify nodes that don’t have parents or only have 1 parent. The data would be presented to you as a 2D array and be similar to the following:

     1   4   8   10
      \ / \ / \ /
       3   5   2
      /     \
     7       9

In this example nodes 1, 4, 8, and 10 have no parents. Nodes 7 and 9 have only one parent.

So how would we do this?

There are many approaches, but a simple approach would be to just use a HashMap to map the tree and the number of parents. Then use that HashMap to understand situations when you have 1 parent vs no parents.

Here’s the total code (including a main method):

    public static void main(String [] args) {

        int[][] children = new int[][]{
            {1, 3}, {3, 7}, {4,3}, {4, 5},
            {8, 5}, {8, 2}, {5, 9}, {10, 2}
        };

        Map<String, List<Integer>> oneZero = findParents(children);

        for(Map.Entry<String, List<Integer>> entry: oneZero.entrySet()) {
            System.out.println(entry.getKey());
            for(int value: (ArrayList<Integer>) entry.getValue()) {
                System.out.print(value + " ");
            }
            System.out.println();
            System.out.println();
        }

    }

    public static Map<String, List<Integer>> findParents(int[][] parentsChild) {

        HashMap<String, List<Integer>> output = new HashMap<String, List<Integer>>();

        HashMap<Integer, Integer> parentsList = new HashMap<Integer, Integer>();

        // capture parent numbers into a HashMap
        for(int row = 0; row < parentsChild.length; row++) {
            if(!parentsList.containsKey(parentsChild[row][1])) {
                parentsList.put(parentsChild[row][1], 1);
            } else {
                parentsList.put(parentsChild[row][1], 2);
            }
        }

        // compare parentslist to original tree to find where there are no parents
        ArrayList<Integer> zeroParent = new ArrayList<Integer>();
        for(int row = 0; row < parentsChild.length; row++) {
            if(!parentsList.containsKey(parentsChild[row][0])) {
                if(!zeroParent.contains(parentsChild[row][0])) {
                    zeroParent.add(parentsChild[row][0]);
                }
            }
        }

        // consult the values in the parent list to identify where there is only 1 parent
        ArrayList<Integer> oneParent = new ArrayList<Integer>();
        for(Map.Entry<Integer, Integer> value: parentsList.entrySet()) {
            if((Integer)value.getValue() == 1) {
                oneParent.add(value.getKey());
            }
        }

        // capture output in output
        // these will be printed to the console
        output.put("Zero Parent", zeroParent);
        output.put("One Parent", oneParent);

        return output;
    }

If you notice, the data is passed in as a 2D array. The 2D array is always only going to be of depth 2, so this code takes advantage of that in the initial for loop where it adds a value to the HashMap with a parent total of 1 the first time its found, then makes it a total of 2 if its found again:

        for(int row = 0; row < parentsChild.length; row++) {
            if(!parentsList.containsKey(parentsChild[row][1])) {
                parentsList.put(parentsChild[row][1], 1);
            } else {
                parentsList.put(parentsChild[row][1], 2);
            }
        }

The code here is fairly self explanatory, but the approach of using a HashMap enables you to capture the tree’s relations in a way that answers the original problem. HashMaps are very powerful and I recommend using them for many different problems.

This code shows you one method of using a HashMap, but many times specific languages offer customized classes that force order or other useful mechanisms. Checkout this code yourself and google Java HashMaps for some other cool articles on this topic.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s