Algorithms: Searching an Unbalanced Tree

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):

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:

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.

Originally published at https://rhythmandbinary.com on May 1, 2019.