Tag Archives: java

Solving The Sweet Spots Board Game

Leave a reply

Creating the Android board game, Sweet Spots, was a fun programming exercise, although developing an algorithmic program to solve the board game is in fact more fun.

A good portion of developing a board game is about validating the game state based on the game rules, creating game control logics, and visual look-and-feel. Much of the above is just mechanical programming exercise. On the other hand, solving the game is a vastly different exercise, requiring some algorithmic programming effort.

Sweet Spots under the hood

The game solving application was written in Java, with Ant the build tool. There are only two simple Java classes that constitute the hierarchical structure of the board game: Spot and Board. Another Java class, SweetSpots, consists of the core mechanism for game solving. Source code is available at GitHub.

Spot defines the (x,y)-coordinate position of each of the NxN spots (i.e. cells) on the board of size N. It also has an integer value that represents:

  • empty (i.e. undecided spot)
  • filler (i.e. spot not chosen for treasure chest)
  • target (i.e. spot chosen for a treasure chest)

In addition, it consists of an integer zone-id (0, 1, .., N-1) that represents the N individual zones.

Board defines the board size (N). The existing board game was developed with either 1 or 2 targets (i.e. number of treasure chests) per row/column/zone for a given game. For generality, the Board class consists of separate targets-per-row, targets-per-column and targets-per-zone, although they would all be the same (i.e. 1 or 2) when applying to the existing game version. It was initially generalized to allow rectangular board dimension (i.e. MxN instead of NxN), but was later simplified to square board.

Board also consists of a variable, spots, of type Spot[][] that maintains the game state during a game, and a number of methods for game rule validation. Besides the standard constructor that takes board size and target count parameters, it also has a constructor for cloning itself to keep a snapshot of the board state.

Class SweetSpots is the class embedded with game solving logic. It takes a board-zone file along with target counts that defines a game as input and consists of necessary methods to solve the game. The board-zone file is a text file which contains the zone information of a given game in the form of a matrix with coordinates (0,0) representing the top left-most entry. For instance, a 4×4 board-zone file might have the following content:

0 1 1 2
0 0 1 2
2 2 2 2
2 3 3 2

The matrix of integers represent 4 zones, each represented by an integer (0-3):

zone 0: (0,0), (0,1), (1,1)
zone 1: (1,0), (2,0), (2,1)
zone 2: (3,0), (3,1), (0,2), (1,2), (2,2), (3,2), (0,3), (3,3)
zone 3: (1,3), (2,3)

Class SweetSpots consists of a variable boardStack which is a stack of type LinkedList. The stack maintains a dynamic list of Board instance snapshots saved at various stages of the trial-and-error routine. The trial-and-error process is performed using two key methods, boardwalk() and rollback(). Method boardwalk() walks through each of the NxN spots on the board (hence “board walk”) in accordance with the game rules. Upon failing any of the game rule validation, rollback() handles rolling back to the previous game-solving state recorded in boardStack.

Below are pseudo-code logic for methods boardwalk() and rollback().

boardwalk(game, coordX, coordY): return int
    while not every spot on the entire board has been walked
        if current spot is empty
            if every targetCount per row/col/zone < targetCount per row/col/zone
                if no targets adjacent to current spot
                    create a snapshot of the board
                    push the snapshot to boardStack
                    put a target in current spot and fillers in adjacent spots
                else
                    put a filler in current spot
        if any row/col/zone has fewer empty spots to satisfy fulfilling targetCount
            return failure
        else // current cell is not empty
            return success
        go to next spot on the board
rollback(): return Board
    if boardStack is empty
        return null
    else
        pop the last saved board from boardStack
        locate the first empty spot
        if every spot on the board has been walked
            return null
        else
            put a filler in current spot
            return board

Solving a game

Class SolveGame is a simple executable module that uses the SweetSpots class to solve a game with defined zone data.

The main flow logic boils down to the following:

static boolean traceOn;
Board game = new Board(boardSize, targetsPerRow, targetsPerCol, targetsPerZone);
SweetSpots ss = new SweetSpots(traceOn);
...
while (ss.boardwalk(game, 0, 0) != 1) {
    game = ss.rollback();
    if (game == null) {
        break;
    }
}

To solve a game with defined zones, simply navigate to the main subdirectory of the java app and run the following command:

java -cp  com.genuine.game.sweetspots.SolveGame <trace?1:0> <boardZoneFile> <boardSize> <targetsPerRow> <targetsPerCol> <targetsPerZone>

For instance, to solve a game defined in ./gamefiles/game-4-1.txt, simply navigate to the main subdirectory of the java app and run the following command from /path/to/sweetspot/java/:

java -cp build/sweetspots-r1.0.0.jar com.genuine.game.sweetspots.SolveGame 0 ./gamefiles/game-4-1.txt 4 1 1 1

Creating a game

Class CreateGame is an executable module that creates a game by generating random zone data and guaranteeing a solution via repetitive method trials in class SweetSpots.

Creating a game for a given board size (i.e. N) and target count involves:

  • generating N random contiguous zones that patition the board, and,
  • ensuring there is a solution for the generated zones

Getting slightly more granular, it involves the following steps:

  1. Assign individual zones random sizes to fill the entire board: To reduce frequency of having extreme zone size, a simplistic weighted random probability distribution, triangularProbDist(), is used for determining the size for individual zones.
  2. For each zone, assign random contiguous spots of the assigned size on the board: Within class CreateGame is a method, zoneWalk(), which essentially “walks” row-wise or column-wise randomly till the assigned zone size is reached. Failure at any point of time to proceed further to cover the entire board with the zones will promptly force a return to step #1.
  3. Transpose the board to further randomize the zone-walk result.
  4. Repeat the above steps till the zones of assigned sizes successfully fill the entire board.
  5. Ensure that there is a solution for the created zones: This is achieved by essentially employing the same game solving logic used in SolveGame.

To create a game that consists of a solution, navigate to the main subdirectory of the java app and execute the following command:

java -cp  com.genuine.game.sweetspots.CreateGame <trace?1:0> <boardZoneFile> <boardSize> <targetsPerRow> <targetsPerCol> <targetsPerZone>

To create a game with 4×4 board size, go to /path/to/sweetspot/java/ and run the following command to generate the game zones in ./gamefiles/:

java -cp build/sweetspots-r1.0.0.jar com.genuine.game.sweetspots.CreateGame 0 ./gamefiles/game-4-1.txt 4 1 1 1

The generated game-zone file should look something like the following:

0 1 1 2
0 0 1 2
2 2 2 2
2 3 3 2

The above Java applications were developed back in Summer of 2013. Though some refactoring effort has been made, there is certainly room for improvement in different areas. In particular, the zone creation piece can be designed to be more robust, ideally enforcing a unique solution for the game. That would be something for a different time perhaps in the near future. Meanwhile, enjoy the board game, which can be downloaded from Google Play.

NIO-based Reactor

5 Replies

Over the past few years, event-based architecture with non-blocking operations has been the norm for high-concurrency server architecture. The per-connection threading (process-based) architecture is no longer favored as an efficient design, especially for handling high volume of concurrent connections. The increasing popularity of Nginx and the relative decline of Apache httpd these days demonstrated the trend.

Java New I/O

Java’s NIO (New I/O, a.k.a. Non-blocking I/O) provides a set of APIs to efficiently handle I/O operations. The key ingredients of NIO include Buffer, Channel and Selector. A NIO Buffer virtually provides direct access to the operating system’s physical memory along with a rich set of methods for alignment and paging of the selected memory that stores any primitive-type data of interest. A NIO Channel then serves as the conduit for bulk data transfers between the Buffer and the associated entity (e.g. a socket).

A socket channel can be configured in non-blocking mode and events such as reading data from the associated socket no longer block the invoking thread for more time than necessary. Together with the NIO Selector responsible for selecting those of the concurrent events that are ready to be processed, NIO APIs are well equipped to handle event-based operations in an efficient fashion.

Non-blocking vs Asynchronous

Note that non-blocking mode is different from asynchronous mode. In non-blocking mode, a requested operation always returns the result immediately regardless of success or failure, thus freeing the invoking thread from being blocked. In asynchronous mode, a separate thread is used to carry out the requested operation in parallel with the invoking thread. Java 7 enhanced NIO to include support for asynchronous file and socket channels.

Reactor pattern

The Reactor pattern is a popular event-based architecture. Using NIO, implementing a basic event-based server on top of Reactor pattern is pretty straight forward. Appended is a bare minimal Reactor-pattern server consisting of a Reactor class and a Handler class.

The single-threaded Reactor class houses the main dispatcher loop responsible for selecting registered events that are ready for socket read/write operations. Registered with the dispatcher during initialization, the also single-threaded Acceptor is responsible for accepting socket connections requested by clients. Finally, the Handler class takes care of the actual events (read from socket, process data, write to socket) in accordance with its operational state.

Each Handler is associated with a SocketChannel and the Selector maintained by the Reactor class. Both variables are declared immutable for performance as well as allowing access by the inner Runnable class. The handler registers with the dispatcher indicating its interested operation (read or write) and gets dispatched when the associated socket is ready for the operation. The Runnable class forms the worker thread pool and is responsible for data processing (in this simple case, echoing), leaving the Handler thread responsible for just socket read/write.

To test the server, just launch it on a host (e.g. server1.example.com) and run a few telnet instances connecting to the server port (e.g. telnet server1.example.com 9090).

Source code: Reactor.java

package reactor;

import java.io.IOException;
import java.net.InetSocketAddress;
import java.nio.channels.Selector;
import java.nio.channels.SelectionKey;
import java.nio.channels.ServerSocketChannel;
import java.nio.channels.SocketChannel;
import java.util.Iterator;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

class Reactor implements Runnable {
    final Selector selector;
    final ServerSocketChannel serverChannel;
    static final int WORKER_POOL_SIZE = 10;
    static ExecutorService workerPool;

    Reactor(int port) throws IOException {
        selector = Selector.open();
        serverChannel = ServerSocketChannel.open();
        serverChannel.socket().bind(new InetSocketAddress(port));
        serverChannel.configureBlocking(false);

        // Register the server socket channel with interest-set set to ACCEPT operation
        SelectionKey sk = serverChannel.register(selector, SelectionKey.OP_ACCEPT);
        sk.attach(new Acceptor());
    }

    public void run() {
        try {
            while (true) {

                selector.select();
                Iterator it = selector.selectedKeys().iterator();

                while (it.hasNext()) {
                    SelectionKey sk = (SelectionKey) it.next();
                    it.remove();
                    Runnable r = (Runnable) sk.attachment();
                    if (r != null)
                        r.run();
                }
            }
        }
        catch (IOException ex) {
            ex.printStackTrace();
        }
    }

    class Acceptor implements Runnable {
        public void run() {
            try {
                SocketChannel channel = serverChannel.accept();
                if (channel != null)
                    new Handler(selector, channel);
            }
            catch (IOException ex) {
                ex.printStackTrace();
            }
        }
    }

    public static void main(String[] args) {
        workerPool = Executors.newFixedThreadPool(WORKER_POOL_SIZE);

        try {
            new Thread(new Reactor(9090)).start();
        }
        catch (IOException ex) {
            ex.printStackTrace();
        }
    }
}

Source code: Handler.java

package reactor;

import java.io.IOException;
import java.nio.ByteBuffer;
import java.nio.charset.Charset;
import java.nio.channels.Selector;
import java.nio.channels.SelectionKey;
import java.nio.channels.SocketChannel;

class Handler implements Runnable {
    final SocketChannel channel;
    final SelectionKey selKey;

    static final int READ_BUF_SIZE = 1024;
    static final int WRiTE_BUF_SIZE = 1024;
    ByteBuffer readBuf = ByteBuffer.allocate(READ_BUF_SIZE);
    ByteBuffer writeBuf = ByteBuffer.allocate(WRiTE_BUF_SIZE);

    Handler(Selector sel, SocketChannel sc) throws IOException {
        channel = sc;
        channel.configureBlocking(false);

        // Register the socket channel with interest-set set to READ operation
        selKey = channel.register(sel, SelectionKey.OP_READ);
        selKey.attach(this);
        selKey.interestOps(SelectionKey.OP_READ);
        sel.wakeup();
    }

    public void run() {
        try {
            if (selKey.isReadable())
                read();
            else if (selKey.isWritable())
                write();
        }
        catch (IOException ex) {
            ex.printStackTrace();
        }
    }

    // Process data by echoing input to output
    synchronized void process() {
        byte[] bytes;

        readBuf.flip();
        bytes = new byte[readBuf.remaining()];
        readBuf.get(bytes, 0, bytes.length);
        System.out.print("process(): " + new String(bytes, Charset.forName("ISO-8859-1")));

        writeBuf = ByteBuffer.wrap(bytes);

        // Set the key's interest to WRITE operation
        selKey.interestOps(SelectionKey.OP_WRITE);
        selKey.selector().wakeup();
    }

    synchronized void read() throws IOException {
        int numBytes;

        try {
            numBytes = channel.read(readBuf);
            System.out.println("read(): #bytes read into 'readBuf' buffer = " + numBytes);

            if (numBytes == -1) {
                selKey.cancel();
                channel.close();
                System.out.println("read(): client connection might have been dropped!");
            }
            else {
                Reactor.workerPool.execute(new Runnable() {
                    public void run() {
                        process();
                    }
                });
            }
        }
        catch (IOException ex) {
            ex.printStackTrace();
            return;
        }
    }

    void write() throws IOException {
        int numBytes = 0;

        try {
            numBytes = channel.write(writeBuf);
            System.out.println("write(): #bytes read from 'writeBuf' buffer = " + numBytes);

            if (numBytes > 0) {
                readBuf.clear();
                writeBuf.clear();

                // Set the key's interest-set back to READ operation
                selKey.interestOps(SelectionKey.OP_READ);
                selKey.selector().wakeup();
            }
        }
        catch (IOException ex) {
            ex.printStackTrace();
        }
    }
}

Programming Exercise – Binary Tree

Leave a reply

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

package bintree;

class Node<E extends Comparable<E>> {
    public E element;
    public Node left;
    public Node right;

    public Node() {
        this(null);
    }

    public Node(E e) {
        element = e;
        left = null;
        right = null;
    }

    boolean isLeaf() {
        return (left == null && right == null);
    }

    public void printNode() {
        if (isLeaf())
            System.out.print(element + "* -> ");
        else
            System.out.print(element + " -> ");
    }
}

BinTree.java – base binary tree class

package bintree;

import java.util.LinkedList;

// BinTree interface
@SuppressWarnings({"unchecked"})
abstract class BinTree<E extends Comparable<E>> {
    public Node root;

    public BinTree() {
        root = null;
    }

    public BinTree(E e) {
        root = new Node(e);
    }

    public boolean isEmpty() {
        return root == null;
    }

    public void addLeft(Node currNode, E e) {
        // CAUTION: this method overwrites left subtree, if exists
        currNode.left = new Node(e);
    }

    public void addRight(Node currNode, E e) {
        // CAUTION: this method overwrites right subtree, if exists
        currNode.right = new Node(e);
    }

    public void removeLeft(Node currNode) {
        if (currNode.left != null) {
            currNode.left = null;
        }
    }

    public void removeRight(Node currNode) {
        if (currNode.right != null) {
            currNode.right = null;
        }
    }

    // Search the subtree under the current node for matching data
    // (Applicable to Binary Search Tree only)
    public abstract boolean search(Node currNode, E e);

    // Insert a node into the subtree under the current node
    // (Applicable to Binary Search Tree only)
    public abstract void insert(Node currNode, E e);

    // Delete the first node found with matching data by replacing it with the
    // max-value node in the branch to the left of the found node
    // (Applicable to Binary Search Tree only)
    public abstract boolean deleteFirst(Node currNode, E e);

    public abstract int size(Node currNode);

    public abstract int height(Node currNode);

    public Node rotateLeft(Node currNode) {
        Node tempNode = currNode.right;
        currNode.right = tempNode.left;
        tempNode.left = currNode;
        return tempNode;  // New root node
    }

    public Node rotateRight(Node currNode) {
        Node tempNode = currNode.left;
        currNode.left = tempNode.right;
        tempNode.right = currNode;
        return tempNode;  // New root node
    }

    // In-order traversal
    public abstract void traverseIn(Node currNode);

    // Pre-order traversal
    public abstract void traversePre(Node currNode);

    // Post-order traversal
    public abstract void traversePost(Node currNode);

    public void printNodeEnd() {
        System.out.println("(end)");
    }
}

BinTreeR.java – binary tree class using recursive methods

package bintree;

import java.util.LinkedList;

// BinTree class using recursive methods
@SuppressWarnings({"unchecked"})
class BinTreeR<E extends Comparable<E>> extends BinTree<E> {
    public Node root;

    public BinTreeR() {
        super();
    }

    public BinTreeR(E e) {
        super(e);
    }

    public boolean isEmpty() {
        return super.isEmpty();
    }

    public void addLeft(Node currNode, E e) {
        super.addLeft(currNode, e);
    }

    public void addRight(Node currNode, E e) {
        super.addRight(currNode, e);
    }

    public void removeLeft(Node currNode) {
        super.removeLeft(currNode);
    }

    public void removeRight(Node currNode) {
        super.removeRight(currNode);
    }

    // Search the subtree under the current node for matching data
    // (Applicable to Binary Search Tree only)
    public boolean search(Node currNode, E e) {
        if (currNode == null) {
            return false;
        }
        else {
            if (((Comparable) e).compareTo(currNode.element) == 0) {
                return true;
            }
            else {
                if (((Comparable) e).compareTo(currNode.element) < 0)
                    return search(currNode.left, e);            
                else
                    return search(currNode.right, e);         
            }
        }
    }

    // Insert a node into the subtree under the current node
    // (Applicable to Binary Search Tree only)
    public void insert(Node currNode, E e) {
        if (currNode == null)  // Do nothing if the input node is null
            return;

        if (((Comparable) e).compareTo(currNode.element) <= 0) {
            if (currNode.left == null)
                currNode.left = new Node(e);
            else
                insert(currNode.left, e);            
        }
        else {
            if (currNode.right == null)
                currNode.right = new Node(e);
            else
                insert(currNode.right, e);            
        }
    }

    // Delete the first node found with matching data in the subtree under the current node
    // by replacing it with the max-value node in the branch to the left of the found node
    // (Applicable to Binary Search Tree only)
    public boolean deleteFirst(Node currNode, E e) {
        return deleteFirst(currNode, null, true, e);
    }

    // deleteFirst helper recursive method carrying parentNode
    public boolean deleteFirst(Node currNode, Node parentNode, boolean onLeft, E e) {
        if (currNode == null) {
            return false;
        }
        else {
            if (((Comparable) e).compareTo(currNode.element) == 0) {
                if (currNode.left == null) {
                    if (onLeft)
                        parentNode.left = currNode.right;
                    else
                        parentNode.right = currNode.right;
                }
                else if (currNode.right == null) {
                    if (onLeft)
                        parentNode.left = currNode.left;
                    else
                        parentNode.right = currNode.left;
                }
                else {
                    // currNode takes data of maxNode on currNode's left branch and remove maxNode
                    Node maxNode = currNode.left;
                    Node maxNodeParent = currNode;

                    if (maxNode.right == null) {
                        currNode.element = maxNode.element;
                        maxNodeParent.left = maxNode.left;
                    }
                    else {
                        while (maxNode.right != null) {
                            maxNodeParent = maxNode;
                            maxNode = maxNode.right;
                        }
                        currNode.element = maxNode.element;
                        maxNodeParent.right = null;
                    }
                }
                return true;
            }
            else {
                if (((Comparable) e).compareTo(currNode.element) < 0) {
                    onLeft = true;
                    return deleteFirst(currNode.left, currNode, onLeft, e);
                }
                else {
                    onLeft = false;
                    return deleteFirst(currNode.right, currNode, onLeft, e);
                }
            }
        }
    }

    public int size(Node currNode) {
        if (currNode == null)
            return 0;
        else
            return (size(currNode.left) + size(currNode.right) + 1);
    }

    public int height(Node currNode) {
        if (currNode == null)
            return -1;
        else
            return (Math.max(height(currNode.left), height(currNode.right)) + 1);
    }

    public Node rotateLeft(Node currNode) {
        return super.rotateLeft(currNode);
    }

    public Node rotateRight(Node currNode) {
        return super.rotateRight(currNode);
    }

    // In-order traversal (recursive)
    public void traverseIn(Node currNode) {
        if(currNode == null) {
            return;
        }
        else {
            traverseIn(currNode.left);
            currNode.printNode();
            traverseIn(currNode.right);
        }
    }

    // Pre-order traversal (recursive)
    public void traversePre(Node currNode) {
        if(currNode == null) {
            return;
        }
        else {
            currNode.printNode();
            traversePre(currNode.left);
            traversePre(currNode.right);
        }
    }

    // Post-order traversal (recursive)
    public void traversePost(Node currNode) {
        if(currNode == null) {
            return;
        }
        else {
            traversePost(currNode.left);
            traversePost(currNode.right);
            currNode.printNode();
        }
    }

    public void printNodeEnd() {
        super.printNodeEnd();
    }
}

BinTreeI.java – binary tree class using iterative methods

package bintree;

import java.util.LinkedList;

// BinTree class using iterative methods
@SuppressWarnings({"unchecked"})
class BinTreeI<E extends Comparable<E>> extends BinTree<E> {
    public Node root;

    public BinTreeI() {
        super();
    }

    public BinTreeI(E e) {
        super(e);
    }

    public boolean isEmpty() {
        return super.isEmpty();
    }

    public void addLeft(Node currNode, E e) {
        super.addLeft(currNode, e);
    }

    public void addRight(Node currNode, E e) {
        super.addRight(currNode, e);
    }

    public void removeLeft(Node currNode) {
        super.removeLeft(currNode);
    }

    public void removeRight(Node currNode) {
        super.removeRight(currNode);
    }

    // Search the subtree under the current node for matching data
    // (Applicable to Binary Search Tree only)
    public boolean search(Node currNode, E e) {
        if (currNode == null)
            return false;

        while (currNode != null) {
            if (((Comparable) e).compareTo(currNode.element) == 0) {
                return true;
            }
            else {
                if (((Comparable) e).compareTo(currNode.element) < 0) {
                    currNode = currNode.left;
                }
                else {
                    currNode = currNode.right;
                }
            }
        }
        return false;
    }
    // Insert a node into the subtree under the current node
    // (Applicable to Binary Search Tree only)
    public void insert(Node currNode, E e) {
        if (currNode == null)  // Do nothing if the input node is null
            return;

        while (currNode != null) {
            if (((Comparable) e).compareTo(currNode.element) <= 0) {
                if (currNode.left != null)
                    currNode = currNode.left;
                else {
                    currNode.left = new Node(e);
                    break;
                }
            }
            else {
                if (currNode.right != null)
                    currNode = currNode.right;
                else {
                    currNode.right = new Node(e);
                    break;
                }
            }
        }
    }

    // Delete the first node found with matching data in the subtree under the current node
    // by replacing it with the max-value node in the branch to the left of the found node
    // (Applicable to Binary Search Tree only)
    public boolean deleteFirst(Node currNode, E e) {
        if (currNode == null)  // Do nothing if the input node is null
            return false;

        boolean onLeft = true;
        Node parentNode = null;

        // Search for the first node with matching data
        while (currNode != null) {
            if (((Comparable) e).compareTo(currNode.element) == 0) {
                break;
            }
            else {
                parentNode = currNode;
                if (((Comparable) e).compareTo(currNode.element) < 0) {
                    onLeft = true;
                    currNode = currNode.left;
                }
                else {
                    onLeft = false;
                    currNode = currNode.right;
                }
            }
        }

        if (currNode == null) {  // No node with matching data
            return false;
        }
        else {
            if (currNode.left == null) {
                // Remove currNode
                if (onLeft)
                    parentNode.left = currNode.right;
                else
                    parentNode.right = currNode.right;
            }
            else if (currNode.right == null) {
                // Remove currNode
                if (onLeft)
                    parentNode.left = currNode.left;
                else
                    parentNode.right = currNode.left;
            }
            else {
                // currNode takes data of maxNode on currNode's left branch and remove maxNode
                Node maxNode = currNode.left;
                Node maxNodeParent = currNode;

                if (maxNode.right == null) {
                    currNode.element = maxNode.element;
                    maxNodeParent.left = maxNode.left;
                }
                else {
                    while (maxNode.right != null) {
                        maxNodeParent = maxNode;
                        maxNode = maxNode.right;
                    }
                    currNode.element = maxNode.element;
                    maxNodeParent.right = null;
                }
            }
        }
        return true;
    }

    // Calculate tree size using in-order traversal logic
    public int size(Node currNode) {
        LinkedList<Node> stack = new LinkedList<Node>();
        int nodeCount = 0;

        while (currNode != null || !stack.isEmpty()) {
            if (currNode != null) {
                stack.push(currNode);
                currNode = currNode.left;
            }
            else {
                currNode = stack.pop();
                nodeCount++;
                currNode = currNode.right;
            }
        }
        return nodeCount;
    }

    // Calculate tree height using post-order traversal logic
    public int height(Node currNode) {
        LinkedList<Node> stack = new LinkedList<Node>();
        Node prevNode = null;
        int maxCount = 0;

        if (currNode == null)
            return -1;
        stack.push(currNode);

        while (!stack.isEmpty()) {
            currNode = stack.peek();
            // Traversing down the tree from left or right
            if (prevNode == null || currNode == prevNode.left || currNode == prevNode.right) {
                if (currNode.left != null)
                    stack.push(currNode.left);
                else if (currNode.right != null)
                    stack.push(currNode.right);
            }
            // Traversing up the tree from the left
            else if (currNode.left == prevNode) {
                if (currNode.right != null)
                    stack.push(currNode.right);
            }
            // Traversing up the tree from the right, at a leaf node or otherwise
            else {
                currNode = stack.pop();
            }
            prevNode = currNode;
            if (stack.size() > maxCount)
                maxCount = stack.size();
        }
        return maxCount - 1;
    }

    public Node rotateLeft(Node currNode) {
        return super.rotateLeft(currNode);
    }

    public Node rotateRight(Node currNode) {
        return super.rotateRight(currNode);
    }

    // In-order traversal
    public void traverseIn(Node currNode) {
        LinkedList<Node> stack = new LinkedList<Node>();

        while (currNode != null || !stack.isEmpty()) {
            if (currNode != null) {
                stack.push(currNode);
                currNode = currNode.left;
            }
            else {
                currNode = stack.pop();
                currNode.printNode();
                currNode = currNode.right;
            }
        }
        printNodeEnd();
    }

    // Pre-order traversal
    public void traversePre(Node currNode) {
        LinkedList<Node> stack = new LinkedList<Node>();

        while (currNode != null || !stack.isEmpty()) {
            if (currNode != null) {
                stack.push(currNode);
                currNode.printNode();
                currNode = currNode.left;
            }
            else {
                currNode = stack.pop();
                currNode = currNode.right;
            }
        }
        printNodeEnd();
    }

    // Post-order traversal using a single stack
    public void traversePost(Node currNode) {
        LinkedList<Node> stack = new LinkedList<Node>();
        Node prevNode = null;

        if (currNode == null)
            return;
        stack.push(currNode);

        while (!stack.isEmpty()) {
            currNode = stack.peek();
            // Traversing down the tree from left or right
            if (prevNode == null || currNode == prevNode.left || currNode == prevNode.right) {
                if (currNode.left != null)
                    stack.push(currNode.left);
                else if (currNode.right != null)
                    stack.push(currNode.right);
            }
            // Traversing up the tree from the left
            else if (currNode.left == prevNode) {
                if (currNode.right != null)
                    stack.push(currNode.right);
            }
            // Traversing up the tree from the right or otherwise
            else {
                currNode.printNode();
                currNode = stack.pop();
            }
            prevNode = currNode;
        }
        printNodeEnd();
    }

    /*
    // Post-order traversal using two stacks
    public void traversePost(Node currNode) {
        LinkedList<Node> inStack = new LinkedList<Node>();
        LinkedList<Node> outStack = new LinkedList<Node>();

        if (currNode == null)
            return;
        inStack.push(currNode);

        while (!inStack.isEmpty()) {
            currNode = inStack.pop();
            outStack.push(currNode);
            if (currNode.left != null)
                inStack.push(currNode.left);
            if (currNode.right != null)
                inStack.push(currNode.right);
        }

        while (!outStack.isEmpty()) {
            currNode = outStack.pop();
            currNode.printNode();
        }
        printNodeEnd();
    }
    */

    public void printNodeEnd() {
        super.printNodeEnd();
    }
}

BinTreeMain.java – test application

package bintree;

import java.io.*;
import java.util.*;

class BinTreeMain {

    @SuppressWarnings({"unchecked"})
    public static void main(String[] args) {
        if (args.length != 1 || !args[0].matches("[iIrR]")) {
            System.out.println("Usage: java -cp build/bintree-r1.0.0.jar bintree.BinTreeMain I|R (Iterative or Recursive)");
            System.out.println("  e.g. java -cp build/bintree-r1.0.0.jar bintree.BinTreeMain R");
            System.exit(0);
        }

        BinTree tree = null;

        boolean useRecurMethods = args[0].matches("[rR]");
        if (!useRecurMethods) {
            tree = new BinTreeI();
        }
        else {
            tree = new BinTreeR();
        }

        /* Tree content

                      (E)
                     /   \
                   /       \
                (C)         (H)
               /   \       /   \
            (B)    (D)  (G)     (J)
           /           /       /
        (A)         (F)     (I)
                           /   \
                       (HH)     (II)

        */

        tree.root = new Node("E");

        // Test insert
        tree.insert(tree.root, "H");
        tree.insert(tree.root, "C");
        tree.insert(tree.root, "D");
        tree.insert(tree.root, "G");
        tree.insert(tree.root, "B");
        tree.insert(tree.root, "J");
        tree.insert(tree.root, "F");
        tree.insert(tree.root, "A");
        tree.insert(tree.root, "I");
        tree.insert(tree.root, "HH");
        tree.insert(tree.root, "II");

        // Test search
        System.out.println("Result: " + (tree.search(tree.root, "G") ? "Found!" : "Not found!"));
        System.out.println("Result: " + (tree.search(tree.root, "FF") ? "Found!" : "Not found!"));

        System.out.println("\nTraversing tree from root ...");
        tree.traverseIn(tree.root);
        if (useRecurMethods) tree.printNodeEnd();
        System.out.println("\nSize of tree: " + tree.size(tree.root));
        System.out.println("Height of tree: " + tree.height(tree.root));

        // Test delete
        System.out.println("\nDeleting first node containing B from root ...");
        System.out.println("Result: " + (tree.deleteFirst(tree.root, "B") ? "Found and deleted!" : "Not found!"));

        System.out.println("\nDeleting first node containing CC from root ...");
        System.out.println("Result: " + (tree.deleteFirst(tree.root, "CC") ? "Found and deleted!" : "Not found!"));

        System.out.println("\nDeleting first node containing H from root ...");
        System.out.println("Result: " + (tree.deleteFirst(tree.root, "H") ? "Found and deleted!" : "Not found!"));

        System.out.println("\nDeleting first node containing J from root ...");
        System.out.println("Result: " + (tree.deleteFirst(tree.root, "J") ? "Found and deleted!" : "Not found!"));

        System.out.println("\nDeleting first node containing E (root node) from root ...");
        System.out.println("Result: " + (tree.deleteFirst(tree.root, "E") ? "Found and deleted!" : "Not found!"));
        System.out.println("Root node now has data " + tree.root.element);

        System.out.println("\nTraversing tree from root ...");
        tree.traverseIn(tree.root);
        if (useRecurMethods) tree.printNodeEnd();
        System.out.println("\nSize of tree: " + tree.size(tree.root));
        System.out.println("Height of tree: " + tree.height(tree.root));
    }
}