Rolling Binary Trees: A Guide to Common Design Patterns in Java

Introduction

Binary trees are fundamental data structures, ubiquitous in computer science and software engineering. We use them to represent hierarchical data and implement more complex data structures, such as search trees, syntax trees, cryptographic hash trees, space partitioning trees, heaps, and so on. Common binary tree operations include insertion, deletion, rotation, traversal, and searching.

A relatively uncommon and unexplored operation is roll (or rolling), which modifies the structure of a binary tree in such a way that, when visualized, the newly obtained structure appears to be rolled at a 90-degree angle, either clockwise or counterclockwise. This gives us two variants of the roll operation — clockwise roll (CR) and counterclockwise roll (CCR).

Unlike rotation, which renders the inorder traversal of a binary tree invariant, rolling a binary tree produces a new binary tree whose inorder traversal is identical to (a) the postorder traversal of the original tree, if rolled clockwise; or (b) the preorder traversal of the original tree, if rolled counterclockwise. Inversely, the inorder traversal of the original tree becomes (a) the preorder traversal of the clockwise-rolled tree, or (b) the postorder traversal of the counterclockwise-rolled tree. Formally, we can define the roll operation in terms of these traversals, as follows:

• CR(T1) = (T2) ↔ Postorder(T1) = Inorder(T2) & Inorder(T1) = Preorder(T2)
• CCR(T1) = (T2) ↔ Preorder(T1) = Inorder(T2) & Inorder(T1) = Postorder(T2)

where T1 is the original tree, T2 is the rolled tree, and ↔ denotes equivalence.

The two roll variants are inverse to one another, i.e., applying the roll operation to a binary tree twice in succession in opposite directions always produces the original tree. And the roll operation is non-idempotent, i.e., applying it twice in succession in the same direction does not produce the original tree, except in the trivial case of a tree with a single node.

Binary tree roll examples

Below is a simple illustration of a binary tree (T1) and its clockwise-rolled counterpart (T2) to its right. From the inverse nature of the roll variants, It also follows that T1 is the counterclockwise-rolled counterpart of T2.

In some cases, when the topology of the tree is such that when viewed at a ±90° angle it appears as though certain nodes have two parents, the visual effect of the roll operation may lose its acuity. Nevertheless, the equivalence between the correlated traversals always holds. For instance, consider the binary tree T2 from the previous example and its clockwise-rolled counterpart T3 shown below.

If we compare T3 to a literal -90° view of T2, we can observe that the subtrees rooted at ④ and ⑥ appear to be "pulled down" to create a proper binary tree structure. A similar thing happens when we take T3 from the example above and roll it clockwise.

The subtrees rooted at ④ and ⑥ appear to be adjusted again, to correct for the "double-parent" anomaly.

Pseudocode and complexity

def rollClockwise(root, parent = null) 
    if root != null
        if root.left != null
            rollClockwise(root.left, parent)
            root.left.right = root
            root.left = null
        else if parent != null
            parent.left = root
            parent.right = null
        if root.right != null
            rollClockwise(root.right, root)

We model the roll operation as a recursive algorithm that takes a binary tree (i.e., a reference to its root node) as input and mutates its topology in place. The algorithm traverses the tree in a depth-first manner, removing existing and creating new links between the nodes as it goes. As a result, it produces a modified version of the original tree in accordance with the definition of the roll operation. A special parameter parent is used to anchor subtrees constructed during the recursive traversal to their target parent nodes and effectively rectify the "double-parent" anomaly mentioned previously.

The algorithm has a time complexity of Θ(𝑛), where 𝑛 is the number of nodes in the tree, and its space complexity is proportional to the height of the binary tree (ℎ) as the call stack grows up to ℎ + 1 frames, i.e., Θ(𝑛) in the worst case (for ℎ = 𝑛 - 1) and Θ(log₂ 𝑛) in the best case (for ℎ = ⌊log₂ 𝑛⌋).

For a detailed analysis of this algorithm and its complexity, please refer to the following paper: A linear time algorithm for rolling binary trees.

Implementation

In this section, we are going to present a step by step implementation of the binary tree roll algorithm in Java, by following basic design principles of object-oriented programming and implementing a few design patterns along the way.

Project setup

Let's start by bootstrapping a new Java project using Maven. We are going to use the JUnit 5 framework to test our implementation, so we need to add the following dependency to the pom.xml file of the project:

<dependencies>
  <dependency>
    <groupId>org.junit.jupiter</groupId>
    <artifactId>junit-jupiter</artifactId>
    <version>5.9.2</version>
    <scope>test</scope>
  </dependency>
</dependencies>

Now let's define the basic building blocks of our implementation, i.e., the binary tree data structure and the traversal algorithms.

Static factory methods

We create a simple, recursively defined Node class that holds a value of a generic type T and references to its left and right children.

public class Node<T> {
    private T value;
    private Node<T> left
    private Node<T> right;

    /* constructors, getters, setters, etc. */
}

Then we create a BinaryTree class that holds a reference to the root node of the tree and provides a static factory method for creating new instances of the class from a list of values provided in a nullable level-order traversal format. This format uses a "null identifier" value to denote empty (null) nodes. For example, the sequence [1, 2, 3, -1, -1, 4, 5, -1, 6],  where -1 is the null identifier, represents the following binary tree:

  1
 / \
2   3
   / \
  4   5
   \  
    6

The way we can implement the static factory method is by using a queue to store the nodes of the tree as they are being read from the input sequence. First, we add the root node to the queue. Then, we read the next two values from the input sequence and create the left and right children of the node. If a node value is null, we do not create a child node. We add the newly created children to the queue and repeat this process until we reach the end of the input sequence.

public class BinaryTree<T> {
  
  private Node<T> root;

  private BinaryTree(Node<T> root) {
    this.root = root;
  }

  public static <T> BinaryTree<T> of(T[] values, T nullIdentifier) {
    if (values == null || values.length == 0 || values[0] == nullIdentifier) {
      return new BinaryTree<>();
    }

    Node<T> rootNode = new Node<>(values[0]);
    Queue<Node<T>> nodeQueue = new LinkedList<>();
    nodeQueue.offer(rootNode);

    int valPtr = 1;

    while (!nodeQueue.isEmpty()) {
      T leftVal = (valPtr < values.length) ? values[valPtr++] : null;
      T rightVal = (valPtr < values.length) ? values[valPtr++] : null;
      Node<T> node = nodeQueue.poll();

      if (leftVal != null && !leftVal.equals(nullIdentifier)) {
        Node<T> leftNode = new Node<>(leftVal);
        node.setLeft(leftNode);
        nodeQueue.offer(leftNode);
      }

      if (rightVal != null && !rightVal.equals(nullIdentifier)) {
        Node<T> rightNode = new Node<>(rightVal);
        node.setRight(rightNode);
        nodeQueue.offer(rightNode);
      }
    }

    return new BinaryTree<>(rootNode);
  }
}

For convenience, we are going to create an overloaded version of the static factory method that uses null as the default null identifier value, and a single, varargs input parameter:

public static <T> BinaryTree<T> of(T... values) {
  return of(values, null);
}

The Visitor pattern

Another essential feature we need is a way to obtain the preorder, inorder, and postorder traversals of the binary tree. We can implement this functionality by using the Visitor design pattern, which will allow us to separate the traversal algorithms from the binary tree data structure.

First, we define an interface for the visitor that we will use to traverse the tree nodes:

public interface Visitor<T> {
  void visit(BinaryTree.Node<T> node);
}

Then, we create three concrete implementations of the Visitor interface, one for each of the three traversal orders. We want these visitors to store the nodes in a list in the order in which they are visited. And since the action we want to perform on the nodes (i.e., adding them to a list) is the same for all traversals, we implement it with a separate interface, called VisitorAction, and pass it to the visitors as a constructor argument. This allows us to decouple the traversal logic from the action we perform on the visited nodes, which makes the code cleaner and more flexible.

The implementation of the VisitorAction interface and one of the concrete visitors is shown below. We extend Java's Consumer functional interface to allow custom actions and composed (chained) consumers to be passed at runtime.

public interface VisitorAction<T> extends Consumer<Node<T>> {
  @Override
  default VisitorAction<T> andThen(Consumer<? super Node<T>> after) {
    return Consumer.super.andThen(after)::accept;
  }
}

public final class PreorderVisitor<T> implements Visitor<T> {
  private final VisitorAction<T> action;

  public PreorderVisitor(VisitorAction<T> action) {
    this.action = action;
  }

  public VisitorAction<T> action() {
    return action;
  }

  @Override
  public void visit(Node<T> root) {
    if (root != null) {
      action.accept(root);
      this.visit(root.getLeft());
      this.visit(root.getRight());
    }
  }
}

We can now define the action for adding the visited nodes to a list, which we are going to pass to the visitors as a constructor argument:

public class NodeCollectorVisitorAction<T> implements VisitorAction<T> {

  private final List<T> list;

  public NodeCollectorVisitorAction() {
    this.list = new ArrayList<>();
  }

  public List<T> getList() {
    return list;
  }

  @Override
  public void accept(BinaryTree.Node<T> node) {
    list.add(node.getValue());
  }
}

To complete the traversal functionality, we add a traverse() method to the BinaryTree class that accepts a visitor as an argument and calls its visit() method on the root node of the tree:

public class BinaryTree<T> {
  /* ... */

  public void traverse(Visitor<T> visitor) {
    visitor.visit(this.root);
  }
}

Before we move on to the implementation of the roll operation, let's create a simple test for the BinaryTree class to make sure that the tree is created correctly from the input sequence:

@Test
void testStaticFactoryMethodAndTraversals() {
  Integer[] values = {1, 2, 3, null, null, 4, 5, null, 6};
  BinaryTree<Integer> tree = BinaryTree.of(values);

  var preorderCollector = new NodeCollectorVisitorAction<Integer>();
  var inorderCollector = new NodeCollectorVisitorAction<Integer>();
  var postorderCollector = new NodeCollectorVisitorAction<Integer>();

  tree.traverse(new PreorderVisitor<>(preorderCollector));
  tree.traverse(new InorderVisitor<>(inorderCollector));
  tree.traverse(new PostorderVisitor<>(postorderCollector));

  var expectedPreorder = List.of(1, 2, 3, 4, 6, 5);
  var expectedInorder = List.of(2, 1, 4, 6, 3, 5);
  var expectedPostorder = List.of(2, 6, 4, 5, 3, 1);

  assertEquals(expectedPreorder, preorderCollector.getList());
  assertEquals(expectedInorder, inorderCollector.getList());
  assertEquals(expectedPostorder, postorderCollector.getList());
}

And let's also demonstrate the flexibility of our traversing visitors:

@Test
void testTraversalVisitorActions() {
  var tree = BinaryTree.of("Friends", "Jay", "Open", "Foo", "IO", "Of", "JDK");
  var stringBuilder = new StringBuilder();

  var append = (VisitorAction<String>) node -> stringBuilder.append(node.getValue());
  var punctuate = (VisitorAction<String>) node -> {
    switch (node.getValue()) {
      case "Jay" -> stringBuilder.append(".");
      case "IO" -> stringBuilder.append(" — ");
      case "Friends", "Of" -> stringBuilder.append(" ");
    }
  };

  tree.traverse(new InorderVisitor<>(append.andThen(punctuate)));
  System.out.println(stringBuilder);
}

FooJay.IO — Friends Of OpenJDK

The binary tree roll algorithm

To implement the algorithm for rolling binary trees, we need to consider the two roll directions, clockwise and counterclockwise. We also need to take into account the fact that, in most cases, the root node of the rolled tree is not going to be the same as the root node of the original tree.

This means that we need to implement a mechanism to identify and store a reference to the root node of the rolled tree. A good way to do this would be by creating an abstract class called RollHandler, which we can use as a base class for the concrete implementations of the algorithm.

abstract class RollHandler<T> {

  private BinaryTreeNode<T> rolledRoot;

  public BinaryTreeNode<T> getRolledRoot() {
    return rolledRoot;
  }

  public void setRolledRoot(BinaryTreeNode<T> rolledRoot) {
    this.rolledRoot = rolledRoot;
  }

  abstract void roll(BinaryTreeNode<T> root, BinaryTreeNode<T> parent);
}

We will implement the roll() method for the clockwise and the counterclockwise roll variants separately, and have these implementations use the rolledRoot field to assign a reference to the rolled tree's root node.

We can identify the rolled tree's root node when the recursive traversal reaches either the leftmost or the rightmost node of the original tree, depending on the roll direction. This means that we can obtain a reference to it in the else block of the algorithm, when we have reached a node without a left child (when performing the clockwise roll) or without a right child (when performing the counterclockwise roll), and when the parent argument is also null. The latter condition ensures that we have reached the leftmost (or the rightmost) node of the original tree, rather than one of its subtrees.

The implementation of the roll() method for the clockwise and counterclockwise roll handlers will, therefore, look something like this:

class ClockwiseRollHandler<T> extends RollHandler<T> {

  @Override
  public void roll(BinaryTree.Node<T> root, BinaryTree.Node<T> parent) {
    if (root != null) {
      if (root.getLeft() != null) {
        this.roll(root.getLeft(), parent);
        root.getLeft().setRight(root);
        root.setLeft(null);
      } else {
        if (parent != null) {
          parent.setLeft(root);
          parent.setRight(null);
        } else {
          this.setRolledRoot(root);
        }
      }

      if (root.getRight() != null) {
        this.roll(root.getRight(), root);
      }
    }
  }
}

class CounterclockwiseRollHandler<T> extends RollHandler<T> {

  @Override
  public void roll(BinaryTree.Node<T> root, BinaryTree.Node<T> parent) {
    if (root != null) {
      if (root.getRight() != null) {
        this.roll(root.getRight(), parent);
        root.getRight().setLeft(root);
        root.setRight(null);
      } else {
        if (parent != null) {
          parent.setRight(root);
          parent.setLeft(null);
        } else {
          this.setRolledRoot(root);
        }
      }

      if (root.getLeft() != null) {
        this.roll(root.getLeft(), root);
      }
    }
  }
}

To mutate or not to mutate?

Aside from the two different roll variants, there is another important implementation aspect we need to consider. And that is the fact that mutating the original data structure might not always be desirable.

There might be use cases where we want to preserve the original tree, and for this reason, we will provide two different top-level implementations of the roll algorithm: one that mutates the original tree, and one that preserves the original tree and creates a new one.

A Factory of Strategies

We can combine the Strategy and the Factory design patterns to create the mutating (mutable) and non-mutating (immutable) versions of the clockwise and counterclockwise roll algorithm, and to allow the user to choose the desired implementation at runtime.

First, we define an interface for the roll strategy:

public interface RollStrategy<T> {
  BinaryTree<T> roll(BinaryTree<T> tree);
}

Then, we create two abstract classes that implement the RollStrategy interface and provide two different templates for implementing the roll algorithm. This approach is also known as the Template Method pattern, where an abstract superclass defines the high-level skeleton of an algorithm.

Both templates will have an abstract method to obtain a roll handler. And for the immutable strategy, we will apply the roll() method of the roll handler to a deep copy of the tree, keeping the original tree intact:

abstract class DefaultRollStrategy<T> implements RollStrategy<T> {

  @Override
  public BinaryTree<T> roll(BinaryTree<T> tree){
    var rollHandler = getRollHandler();
    rollHandler.setRolledRoot(null);
    rollHandler.roll(tree.getRoot(), null);
    tree.setRoot(rollHandler.getRolledRoot());
    return tree;
  }

  abstract RollHandler<T> getRollHandler();
}

abstract class ImmutableRollStrategy<T> implements RollStrategy<T> {

  @Override
  public BinaryTree<T> roll(BinaryTree<T> tree) {
    var rollHandler = getRollHandler();
    rollHandler.setRolledRoot(null);
    var treeCopy = tree.deepCopy();
    rollHandler.roll(treeCopy.getRoot(), null);
    treeCopy.setRoot(rollHandler.getRolledRoot());
    return treeCopy;
  }

  abstract RollHandler<T> getRollHandler();
}

The deepCopy() method runs recursively on the root node and creates a deep clone of the tree.

public BinaryTree<T> deepCopy() {
  return new BinaryTree<>(root != null ? root.deepCopy() : null);
}

public Node<T> deepCopy() {
  var copy = new Node<>(this.value);

  if (this.left != null) {
    copy.setLeft(this.left.copy());
  }

  if (this.right != null) {
    copy.setRight(this.right.copy());
  }

  return copy;
}

To combine the mutable and immutable strategy templates with the clockwise and counterclockwise roll handlers, we create concrete roll strategies which extend the abstract RollStrategy classes and implement the getRollHandler() method. For simplicity, we nest the immutable roll strategies inside the default (mutable) roll strategy classes:

final class ClockwiseRollStrategy<T> extends DefaultRollStrategy<T> {

  @Override
  RollHandler<T> getRollHandler() {
    return new ClockwiseRollHandler<>();
  }

  static final class Immutable<T> extends ImmutableRollStrategy<T> {

    @Override
    RollHandler<T> getRollHandler() {
      return new ClockwiseRollHandler<>();
    }
  }
}

final class CounterclockwiseRollStrategy<T> extends DefaultRollStrategy<T> {

  @Override
  RollHandler<T> getRollHandler() {
    return new CounterclockwiseRollHandler<>();
  }

  static final class Immutable<T> extends ImmutableRollStrategy<T> {

    @Override
    RollHandler<T> getRollHandler() {
      return new CounterclockwiseRollHandler<>();
    }
  }
}

Next, we create a factory interface that we can use to obtain instances of the roll strategies. We use switch expressions to return a strategy in a concise and elegant way.

public enum RollDirection {
  CLOCKWISE,
  COUNTER_CLOCKWISE
}

public interface RollStrategyFactory {

  static <T> RollStrategy<T> create(RollDirection direction) {
    return switch (direction) {
      case CLOCKWISE -> new ClockwiseRollStrategy<>();
      case COUNTER_CLOCKWISE -> new CounterClockwiseRollStrategy<>();
    };
  }

  static <T> RollStrategy<T> createImmutable(RollDirection direction) {
    return switch (direction) {
      case CLOCKWISE -> new ClockwiseRollStrategy.Immutable<>();
      case COUNTER_CLOCKWISE -> new CounterClockwiseRollStrategy.Immutable<>();
    };
  }
}

Finally, we add a roll() method to the BinaryTree class that accepts a RollStrategy instance as an argument and invokes its roll() method on the tree:

public class BinaryTree<T> {
  /* ... */
  
  public BinaryTree<T> roll(RollStrategy<T> strategy) {
    return strategy.roll(this);
  }
}

Design for extension, or else prohibit it

Rolling a binary tree is a straightforward operation with a finite number of variants, and we have implemented both mutable and immutable versions of these variants, exhausting all possible scenarios. To create a closed hierarchy of roll strategies and prevent side effects that could break the algorithm, we can seal the RollStrategy interface and all abstract classes below it by declaring them sealed.

public sealed interface RollStrategy<T> permits ClockwiseRollStrategy, CounterclockwiseRollStrategy {
  /* ... */
}

abstract sealed class DefaultRollStrategy<T> implements RollStrategy<T> 
    permits ClockwiseRollStrategy, CounterclockwiseRollStrategy {
  /* ... */
}

abstract sealed class ImmutableRollStrategy<T> implements RollStrategy<T> 
    permits ClockwiseRollStrategy.Immutable, CounterClockwiseRollStrategy.Immutable {
  /* ... */
}

abstract sealed class RollHandler<T> permits ClockwiseRollHandler, CounterClockwiseRollHandler {
  /* ... */
}

Testing

We can now use our roll algorithm implementation to roll binary trees clockwise and counterclockwise. But before we do that, let's create a simple helper class that we can use to print binary trees to the console. We will use a basic recursive algorithm that prints the tree in a sideways, left-to-right fashion.

public class BinaryTreePrinter<T> {

  private final PrintStream printStream;
  private final int edgeLength = 4;
  private final String edgeShapes = " ┘┐┤";

  public BinaryTreePrinter(PrintStream printStream) {
    this.printStream = printStream;
  }

  public void printTree(BinaryTree<T> tree) {
    var root = tree.getRoot();

    if (root == null) {
      printStream.println("NULL");
    }

    printStream.println(printTree(root, 1, ""));
  }

  private String printTree(BinaryTree.Node<T> root, int direction, String prefix) {
    if (root == null) {
      return "";
    }

    var edgeType = (root.getRight() != null ? 1 : 0) + (root.getLeft() != null ? 2 : 0);

    var postfix = switch (edgeType) {
      case 1, 2, 3 -> " " + "—".repeat(edgeLength) + edgeShapes.charAt(edgeType) + "\n";
      default -> "\n";
    };

    var padding = " ".repeat(edgeLength + root.getValue().toString().length());

    var printRight = print(root.getRight(), 2, prefix + "│  ".charAt(direction) + padding);
    var printLeft = print(root.getLeft(), 0, prefix + "  │".charAt(direction) + padding);

    return printRight + prefix + root.getValue() + postfix + printLeft;
  }
}

Next, let's set up a test class that we can use to test our complete implementation.

class IntegrationTests<T> {

  private NodeCollectorVisitorAction<T> preorderCollector1, inorderCollector1, postorderCollector1;
  private NodeCollectorVisitorAction<T> preorderCollector2, inorderCollector2, postorderCollector2;

  private final BinaryTreePrinter<T> printer = new BinaryTreePrinter<>(System.out);

  @BeforeEach
  void setUp() {
    preorderCollector1 = new NodeCollectorVisitorAction<>();
    preorderCollector2 = new NodeCollectorVisitorAction<>();
    inorderCollector1 = new NodeCollectorVisitorAction<>();
    inorderCollector2 = new NodeCollectorVisitorAction<>();
    postorderCollector1 = new NodeCollectorVisitorAction<>();
    postorderCollector2 = new NodeCollectorVisitorAction<>();
  }
}

Now, let's create a small binary tree, roll it clockwise, and print the results to the console.

void testClockwiseRoll() {
  var tree = BinaryTree.of("Friends", "Jay", "Open", "Foo", "IO", "Of", "JDK");
  printer.printTree(tree);

  tree.traverse(new PreorderVisitor<String>(preorderCollector1));
  tree.traverse(new InorderVisitor<String>(inorderCollector1));
  tree.traverse(new PostorderVisitor<String>(postorderCollector1));

  System.out.println(preorderCollector1.getList());
  System.out.println(inorderCollector1.getList());
  System.out.println(postorderCollector1.getList());
  System.out.println();

  tree.roll(RollStrategyFactory.create(RollDirection.CLOCKWISE));
  printer.printTree(tree);

  tree.traverse(new PreorderVisitor<String>(preorderCollector2));
  tree.traverse(new InorderVisitor<String>(inorderCollector2));
  tree.traverse(new PostorderVisitor<String>(postorderCollector2));

  System.out.println(preorderCollector2.getList());
  System.out.println(inorderCollector2.getList());
  System.out.println(postorderCollector2.getList());
  System.out.println();
  
  assertEquals(postorderCollector1.getList(), inorderCollector2.getList());
  assertEquals(inorderCollector1.getList(), preorderCollector2.getList());
}

                     JDK
            Open ————┤
            │        Of
Friends ————┤
            │       IO
            Jay ————┤
                    Foo

[Friends, Jay, Foo, IO, Open, Of, JDK]
[Foo, Jay, IO, Friends, Of, Open, JDK]
[Foo, IO, Jay, Of, JDK, Open, Friends]

                Friends ————┐
                │           │      Open ————┐
                │           │      │        JDK
                │           Of ————┘
        Jay ————┤
        │       IO
Foo ————┘

[Foo, Jay, IO, Friends, Of, Open, JDK]
[Foo, IO, Jay, Of, JDK, Open, Friends]
[IO, JDK, Open, Of, Friends, Jay, Foo]

Let's also test the immutable strategy, this time with the counterclockwise roll variant:

void testImmutableCounterClockwiseRoll() {
  var tree = BinaryTree.of("Friends", "Jay", "Open", "Foo", "IO", "Of", "JDK");
  printer.printTree(tree);

  tree.traverse(new PreorderVisitor<>(preorderCollector1));
  tree.traverse(new InorderVisitor<>(inorderCollector1));
  tree.traverse(new PostorderVisitor<>(postorderCollector1));

  System.out.println(preorderCollector1.getList());
  System.out.println(inorderCollector1.getList());
  System.out.println(postorderCollector1.getList());
  System.out.println();

  var rolledTree = tree.roll(RollStrategyFactory.createImmutable(RollDirection.COUNTER_CLOCKWISE));
  printer.printTree(rolledTree);

  rolledTree.traverse(new PreorderVisitor<>(preorderCollector2));
  rolledTree.traverse(new InorderVisitor<>(inorderCollector2));
  rolledTree.traverse(new PostorderVisitor<>(postorderCollector2));

  System.out.println(preorderCollector2.getList());
  System.out.println(inorderCollector2.getList());
  System.out.println(postorderCollector2.getList());
  System.out.println();

  printer.printTree(tree);
  
  assertEquals(preorderCollector1.getList(), inorderCollector2.getList());
  assertEquals(inorderCollector1.getList(), postorderCollector2.getList());
}

                     JDK
            Open ————┤
            │        Of
Friends ————┤
            │       IO
            Jay ————┤
                    Foo

[Friends, Jay, Foo, IO, Open, Of, JDK]
[Foo, Jay, IO, Friends, Of, Open, JDK]
[Foo, IO, Jay, Of, JDK, Open, Friends]

JDK ————┐
        │        Of
        Open ————┤
                 │           IO ————┐
                 │           │      │       Foo
                 │           │      Jay ————┘
                 Friends ————┘

[JDK, Open, Friends, IO, Jay, Foo, Of]
[Friends, Jay, Foo, IO, Open, Of, JDK]
[Foo, Jay, IO, Friends, Of, Open, JDK]

                     JDK
            Open ————┤
            │        Of
Friends ————┤
            │       IO
            Jay ————┤
                    Foo

As we can see, the rolled tree was properly constructed with the immutable strategy, while the original tree remained unchanged.

Summary

In this article, we introduced a linear time algorithm for rolling binary trees and implemented it in Java. We relied on common design patterns and principles to make the implementation clean and flexible.

First, we showed how we can use generics and static factory methods to create data structures, such as binary trees, with a convenient syntax similar to the one used in the Java Collections & Map APIs. Then, we made use of the Visitor pattern to implement the preorder, inorder, and postorder tree traversals. We used the Strategy pattern to implement the clockwise and counterclockwise variants of the binary tree roll algorithm, and we utilized the Template Method pattern to create mutable and immutable versions of each variant. Finally, we used the Factory pattern to expose the roll strategies and made the underlying types sealed to prevent the creation of custom strategies.

To wrap things up, we implemented a helper class to visualize the results of the roll algorithm and used it along with the tree traversals to test the correctness of our implementation.

The complete source code referenced in this article can be found on GitHub.