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, traversal, searching, and rotation.

A relatively uncommon and unexplored operation is rolling, which modifies the structure of a binary tree by shifting the position of its nodes in such a manner that, when visualized, the newly obtained structure appears to be rolled at a 90-degree angle, either clockwise or counterclockwise. Consequently, we have two distinct variants of the roll operation — clockwise roll (CR) and counterclockwise roll (CCR).

Applying the roll transformation to 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 traversal relationships, 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. An immediate consequence of this definition is that the roll operation is (a) idempotent, i.e., applying it twice to the same tree always produces the same result, and (b) symmetric, i.e., rolling a tree clockwise and then counterclockwise, or vice versa, always produces the original tree.

Binary tree roll example

Below is a simple illustration of a binary tree (T1) and its clockwise-rolled counterpart (T2) to its right.

We can also say that the tree on the left (T1) is the counterclockwise-rolled counterpart of the tree on the right (T2).

Roll algorithm pseudocode and complexity

def rollCW(root, parent = null)
if root != null
if root.left != null
rollCW(root.left, parent)
root.left.right = root
root.left = null
else if parent != null
parent.left = root
parent.right = null
if root.right != null
rollCW(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, compliant with the definition of the roll operation we introduced previously. A special parameter parent is used to anchor the parent nodes of subtrees reconstructed during the recursive traversal.

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 Θ(log2𝑛) in the best case (for ℎ = ⌊log2𝑛⌋).

For a more 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 and basic functionality

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.

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 nodes in the tree. 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 final BinaryTreeNode<T> root;

private BinaryTree(BinaryTreeNode<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);
}

Tree traversals

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.

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

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 implementations to store the visited nodes in a list in the order in which we visit them. And since the action we want to perform on the nodes (i.e., adding them to a list) is not directly dependent on the 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.

public interface VisitorAction<T> extends Consumer<BinaryTree.Node<T>> {}

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 Collections.unmodifiableList(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. We will use the preorder, inorder, and postorder traversals to verify that everything works as expected:

public class BinaryTreeTest {

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

var preorderCollector = new NodeCollectorAction<Integer>();
var inorderCollector = new NodeCollectorAction<Integer>();
var postorderCollector = new NodeCollectorAction<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());
}
}

The roll algorithm

To implement the binary tree roll algorithm, we need to consider the two different roll variants: clockwise and counterclockwise. We also need to consider the fact that, in most cases, the root node of the rolled tree will not be the same as the root node of the original tree.

This means that we have to implement a mechanism to identify and store a reference to the root node of the rolled tree. We can do this 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. From the nature of the roll transformation, we can deduce that the rolled tree’s root node will always be either the leftmost or the rightmost node of the original tree, depending on the roll direction. This means that we can identify and assign the rolled tree’s root node in the else block of the roll() method, by checking if the parent argument is null and if the rolledRoot field has not already been assigned. The implementations of the roll() method for the clockwise and counterclockwise roll handler will therefore look 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 if (getRolledRoot() == null) {
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 if (getRolledRoot() == null) {
setRolledRoot(root);
}
}

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

To mutate or not to mutate?

Aside from the two different roll directions, there is another important 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 implementation of the roll algorithm: one that mutates the original tree, and one that creates a new tree.

We can combine the Strategy and the Factory design patterns to create the mutating and non-mutating (i.e., 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 we use an abstract superclass to define 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;
}

Exposing the roll strategies

To create the four possible roll strategy combinations, we create two concrete roll strategies that 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:

class ClockwiseRollStrategy<T> extends DefaultRollStrategy<T> {

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

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

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

class CounterclockwiseRollStrategy<T> extends DefaultRollStrategy<T> {

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

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

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);
}
}

Usage and 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 print(BinaryTree<T> tree) {
var root = tree.getRoot();

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

printStream.println(print(root, 1, “”));
}

private String print(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.print(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.print(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 roll strategy, this time with the counterclockwise variant:

void testImmutableCounterClockwiseRoll() {
var tree = BinaryTree.of(“Friends”, “Jay”, “Open”, “Foo”, “IO”, “Of”, “JDK”);
printer.print(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.print(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.print(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 and returned by the roll method, while the original tree remained unchanged.

Summary

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

First, we showed how we can use 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. 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.

The post Rolling Binary Trees: A Guide to Common Design Patterns in Java appeared first on foojay.