Tag Archives: java generics

Programming Exercise – Binary Tree

Like sorting algorithms, binary tree implementation is another good programming exercise. In particular, methods for traversing a tree, searching nodes in a binary search tree and many other binary tree operations form a great recipe for refreshing one’s programming skills. Appended is an implementation of a pretty comprehensive set of binary tree (and binary search tree) operations in Java.

Iterative and recursive methods for each of the operations are developed and grouped in two separate classes, BinTreeI and BinTreeR. In general, most operations are easier to be implemented using recursive methods. For instance, calculating tree height using iterative method is a rather non-trivial exercise whereas it’s almost an one-liner using recursion. Some of the operations such as searching and inserting a tree node are only applicable to binary search tree (BST), for which in-order tree traversal should be used. For generality, pre-order and post-order traversal methods are also included in the code.

Similar to the implementation of sorting algorithms in a previous blog, Java Generics and Comparable interface are used. If wanted, the underlying tree node could be further expanded to contain more complex node data such as map entries (e.g. with class type <Key extends Comparable<Key>, Value>, and Map.Entry<K,V> data).

Node.java – binary tree node

BinTree.java – base binary tree class

BinTreeR.java – binary tree class using recursive methods

BinTreeI.java – binary tree class using iterative methods

BinTreeMain.java – test application

Programming Exercise – Sorting Algorithm

Unless algorithm development is part of the job, many software engineers use readily available algorithmic methods as needed and rarely need to develop algorithms themselves. I’m not talking about some complicated statistical or machine learning algorithms. Just simple mundane ones such as a sorting algorithm. Even if you don’t need to code algorithms, going back to writing a sorting program can still be a good exercise to review certain basic skills that might not be frequently used in your current day job. It’s a good-sized programming exercise that isn’t too trivial or taking up too much time. It also reminds you some clever (or dumb) tricks on how to perform sorting by means of recursive divide-and-merge, pivot partitioning, etc. And if nothing else, it might help you in your next technical job interview in the near future.

If you’re up for such an exercise, first, look up from Wikipedia or any other suitable source for a sorting algorithm (e.g. Merge Sort, Quick Sort) of your choice to re-familiarize yourself with its underlying mechanism. Next, decide on the scope of the application – for example, do you want an integer-sorting application or something more generic? … etc. Next, pseudo code, pick the programming language of your choice, and go for it.

Appended is a simple implementation of both Merge Sort and Quick Sort in Java. For the convenience of making method calls with varying data types and sorting algorithms, an interface (SimpleSort) and a wrapper (Sorter) are used. Java Generics is used to generalize the sorter for different data types. Adding Generics to a sorting application requires the using of either the Comparable or Comparator interface, as ordering is necessary in sorting. In this example application, the Comparable interface is used since the default ordering is good enough for basic sorting. The overall implementation code is pretty self explanatory.