Saturday, March 11, 2017

Java 8: Tree Traversal Using Streams

It's quite common to traverse a tree using recursion, but with Java 8 it is now possible to lazily traverse a tree using streams.

The class below represents a tree. The stream() method streams the nodes contained in the tree. You can then do all the cool things that you can do with other streams, such as filtering, mapping and collecting!

public class TreeNode<E> {

  private final E data;
  private final List<TreeNode<E>> children;

   * Creates the tree node with the specified data and no children.
   * @param data
  public TreeNode(final E data) { = data;
    this.children = new ArrayList<>();

   * @return the data contained in this node
  public E getData() {
    return data;

   * Adds a child to this tree node.
   * @param data the data to add
  public TreeNode<E> addChild(final E data) {
    final TreeNode<E> toAdd = new TreeNode<>(data);
    return toAdd;

   * @return a stream of nodes in this tree in depth first order
  public Stream<TreeNode<E>> stream() {
    return Stream.concat(Stream.of(this),;

Example usage:

TreeNode<String> root = new TreeNode<>("Root");
TreeNode<String> a = root.addChild("A");
TreeNode<String> c = root.addChild("C");

int count =; // 7

String tree =","));
// Root,A,A1,A2,B,C,C1

Saturday, January 28, 2017

Power Set Algorithm - Iterative

The power set of a set S is the set of all subsets of S including the empty set and S itself. For example, the power set of {1, 2, 3} is {{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.

Previously, I wrote about how you can generate the power set using a recursive algorithm. This time I'll show you how to use iteration.

Recall, that when we are generating a set for the power set, each element can either be in the set or out of the set. In other words, each set can be represented in binary form, where 1 means that the element is in the set and 0 means that it is not. For example, given a set {a, b, c}, the binary string 101 would represent {a, c}.

Generating the power set just comes down to generating all numbers from 0 to 2^n (since there are 2^n possible subsets) and converting the binary representation of the number into the set!

Here is the algorithm:

public static <E> List<List<E>> powerSet(final List<E> list) {
  final List<List<E>> result = new ArrayList<>();
  final int numSubSets = 1 << list.size(); // 2^n
  for (int i = 0; i < numSubSets; i++) {
    final List<E> subSet = new ArrayList<>();
    int index = 0;
    for (int j = i; j > 0; j >>= 1) { // keep shifting right
      if ((j & 1) == 1) { // check last bit
  return result;

Sunday, January 22, 2017

Java 8: Top N elements from a stream

This post shows how you can sort a stream in reverse order and then select the top N elements.

This is quite common in financial systems.

For example, let's say that you have a list of currency exchange rate movements and you want to see the top 5 largest movements. You can do this using Java 8 Streams as shown below:

import static java.util.Comparator.*;
import static*;

// list of currency exchange rate percentage moves
final List<Currency> currencies = Arrays.asList(
    new Currency("EUR/USD", 0.37),
    new Currency("USD/JPY", -0.21),
    new Currency("GBP/USD", 0.27),
    new Currency("AUD/USD", -0.08),
    new Currency("USD/CAD", 0.02),
    new Currency("USD/CHF", -0.46),
    new Currency("EUR/JPY", 0.16),
    new Currency("EUR/GBP", 0.13),
    new Currency("USD/HKD", 0.0),
    new Currency("EUR/CHF", 0.05),
    new Currency("USD/KRW", -0.71)
  .sorted(comparing(Currency::getMove, comparing(Math::abs)).reversed())

The result is:

Currency [ccy=USD/KRW, move=-0.71]
Currency [ccy=USD/CHF, move=-0.46]
Currency [ccy=EUR/USD, move=0.37]
Currency [ccy=GBP/USD, move=0.27]
Currency [ccy=USD/JPY, move=-0.21]

The two argument Comparator.comparing method easily allows us to compare currency moves on absolute value.

Sunday, January 01, 2017 in 2016

Happy 2017, everyone!

I'd like to wish everyone a great start to an even greater new year!

In keeping with tradition, here's one last look back at in 2016.

During 2016, I posted 20 new entries on I am also thrilled that I have more readers from all over the world! Thanks for reading and especially for giving feedback.

Top 5 posts of 2016:

I'm going to be writing a lot more this year, so stay tuned for more great techie tips, tricks and hacks! :)

Related posts: