8
\$\begingroup\$

Given a binary tree (not necessarily a binary search tree), this small Java library implements an algorithm that can neatly print binary trees to text console.

Code

BinaryTreeNode.java

package net.coderodde.util.tree;

/**
 * This interface describes the API for binary tree nodes.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jul 6, 2017)
 * @param <T> the value type.
 */
public interface BinaryTreeNode<T> {

    /**
     * Returns the value of this node.
     * @return the value of this node.
     */
    public T getValue();

    /**
     * Returns the left child of this node or {@code null} if there is no such.
     * @return the left child.
     */
    public BinaryTreeNode<T> getLeftChild();

    /**
     * Returns the right child of this node or {@code null} if there is no such.
     * @return the right child.
     */
    public BinaryTreeNode<T> getRightChild();
}

BinaryTreeNodePrinter.java

package net.coderodde.util.tree;

/**
 * This interface defines the API for binary tree node printers.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jul 6, 2017)
 * @param <T> the type of the binary tree node values.
 */
public interface BinaryTreeNodePrinter<T> {

    /**
     * Returns the text sprite representing only the input node.
     * 
     * @param node the node to convert into a text sprite.
     * @return the text sprite.
     */
    public TextSprite print(BinaryTreeNode<T> node);
}

BinaryTreePrinter.java

package net.coderodde.util.tree;

/**
 * This interface defines the API for printing binary trees textually for 
 * display on console.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jul 6, 2017)
 * @param <T> the type of the binary tree node values.
 */
public interface BinaryTreePrinter<T> {

    /**
     * Prints a binary tree with root node {@code root} using a particular node
     * printer.
     * 
     * @param root        the root node of the tree to print.
     * @param nodePrinter an implementation of the tree node printer.
     * @return the string representation of the tree.
     */
    public String print(BinaryTreeNode<T> root,
                        BinaryTreeNodePrinter<T> nodePrinter);
}

TextSprite.java

package net.coderodde.util.tree;

import java.util.Objects;

/**
 * This class implements the textual sprite used for printing the binary trees.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jul 6, 2017)
 */
public final class TextSprite {

    /**
     * The minimum width of a sprite in characters.
     */
    private static final int MINIMUM_SPRITE_WIDTH = 1;

    /**
     * The minimum height of a sprite in characters.
     */
    private static final int MINIMUM_SPRITE_HEIGHT = 1;

    /**
     * The width of this text sprite.
     */
    private final int width;

    /**
     * The height of this text sprite.
     */
    private final int height;

    /**
     * Contains all the characters.
     */
    private final char[][] window;

    /**
     * Constructs a new empty text sprite.
     * 
     * @param spriteWidth  the number of text columns.
     * @param spriteHeight the number of text rows.
     */
    public TextSprite(int spriteWidth, int spriteHeight) {
        this.width = checkWidth(spriteWidth);
        this.height = checkHeight(spriteHeight);
        this.window = new char[spriteHeight][spriteWidth];
    }

    /**
     * Sets a particular cell to {@code c}.
     * 
     * @param x the x-coordinate of the cell.
     * @param y the y-coordinate of the cell.
     * @param c the character to set.
     */
    public void setChar(int x, int y, char c) {
        checkX(x);
        checkY(y);
        window[y][x] = c;
    }

    /**
     * Reads the content of a particular cell.
     * 
     * @param x the x-coordinate of the cell.
     * @param y the y-coordinate of the cell.
     * @return the contents of the cell.
     */
    public char getChar(int x, int y) {
        checkX(x);
        checkY(y);
        return window[y][x];
    }

    /**
     * Returns the number of columns in this sprite.
     * 
     * @return the number of columns.
     */
    public int getWidth() {
        return width;
    }

    /**
     * Returns the number of rows in this sprite.
     * 
     * @return the number of rows.
     */
    public int getHeight() {
        return height;
    }

    /**
     * Applies the input text sprite on top of a rectangle of this text sprite.
     * 
     * @param textSprite the text sprite to apply.
     * @param xOffset    the horizontal offset from the left border.
     * @param yOffset    the vertical offset from the top border.
     */
    public void apply(TextSprite textSprite, int xOffset, int yOffset) {
        Objects.requireNonNull(textSprite, "The input TextSprite is null!");

        if (xOffset < 0) {
            throw new IndexOutOfBoundsException("xOffset (" + xOffset + ") " +
                    "may not be negative!");
        }

        if (yOffset < 0) {
            throw new IndexOutOfBoundsException("yOffset (" + yOffset + ") " +
                    "may not be negative!");
        }

        if (xOffset + textSprite.getWidth() > getWidth()) {
            throw new IndexOutOfBoundsException("xOffset (" + xOffset + ") " +
                    "is too large! Must be at most " +
                    (getWidth() - textSprite.getWidth()) + ".");
        }

        if (yOffset + textSprite.getHeight() > getHeight()) {
            throw new IndexOutOfBoundsException("yOffset (" + yOffset + ") " +
                    "is too large! Must be at most " +
                    (getHeight() - textSprite.getHeight()) + ".");
        }

        for (int y = 0; y < textSprite.getHeight(); ++y) {
            for (int x = 0; x < textSprite.getWidth(); ++x) {
                setChar(xOffset + x, yOffset + y, textSprite.getChar(x, y));
            }
        }
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder((width + 1) * height - 1);
        String separator = "";

        for (int y = 0; y < height; ++y) {
            sb.append(separator);
            separator = "\n";

            for (int x = 0; x < width; ++x) {
                sb.append(getChar(x, y));
            }
        }

        return sb.toString();
    }

    private int checkWidth(int width) {
        if (width < MINIMUM_SPRITE_WIDTH) {
            throw new IllegalArgumentException(
                    "The sprite width is too small (" + width + "). " +
                    "Must be at least " + MINIMUM_SPRITE_WIDTH + ".");
        }

        return width;
    }

    private int checkHeight(int height) {
        if (height < MINIMUM_SPRITE_HEIGHT) {
            throw new IllegalArgumentException(
                    "The sprite height is too small (" + height + "). " +
                    "Must be at least " + MINIMUM_SPRITE_HEIGHT + ".");
        }

        return height;
    }

    private void checkX(int x) {
        if (x < 0) {
            throw new IndexOutOfBoundsException("x = " + x + " is negative.");
        } else if (x >= width) {
            throw new IndexOutOfBoundsException("x = " + x + " exceeds the " +
                                                "width = " + width);
        }
    }

    private void checkY(int y) {
        if (y < 0) {
            throw new IndexOutOfBoundsException("y = " + y + " is negative.");
        } else if (y >= height) {
            throw new IndexOutOfBoundsException("y = " + y + " exceeds the " +
                                                "height = " + height);
        }
    }
}

DefaultBinaryTreeNodePrinter.java

package net.coderodde.util.tree.support;

import net.coderodde.util.tree.BinaryTreeNode;
import net.coderodde.util.tree.BinaryTreeNodePrinter;
import net.coderodde.util.tree.TextSprite;

/**
 * This class implements a default binary tree node printer.
 * 
 * @author Rodion "rodde" Efremov 
 * @version 1.6 (Jul 6, 2017)
 * @param <T> the type of the binary tree node values.
 */
public final class DefaultBinaryTreeNodePrinter<T> 
        implements BinaryTreeNodePrinter<T> {

    /**
     * The default top padding.
     */
    private static final int DEFAULT_TOP_PADDING = 0;

    /**
     * The default right padding.
     */
    private static final int DEFAULT_RIGHT_PADDING = 0;

    /**
     * The default bottom padding.
     */
    private static final int DEFAULT_BOTTOM_PADDING = 0;

    /**
     * The default left padding.
     */
    private static final int DEFAULT_LEFT_PADDING = 0;

    /**
     * The default character used to print node corners.
     */
    private static final char DEFAULT_CORNER_CHARACTER = '+';

    /**
     * The default character used to print horizontal node borders.
     */
    private static final char DEFAULT_HORIZONTAL_BORDER_CHARACTER = '-';

    /**
     * The default character used to print vertical node borders.
     */
    private static final char DEFAULT_VERTICAL_BORDER_CHARACTER = '|';

    /**
     * The top padding.
     */
    private int paddingTop = DEFAULT_TOP_PADDING;

    /**
     * The right padding.
     */
    private int paddingRight = DEFAULT_RIGHT_PADDING;

    /**
     * The bottom padding.
     */
    private int paddingBottom = DEFAULT_BOTTOM_PADDING;

    /**
     * The left padding.
     */
    private int paddingLeft = DEFAULT_LEFT_PADDING;

    /**
     * The character used to represent top left corners.
     */
    private char topLeftCornerCharacter = DEFAULT_CORNER_CHARACTER;

    /**
     * The character used to represent top right corners.
     */
    private char topRightCornerCharacter = DEFAULT_CORNER_CHARACTER;

    /**
     * The character used to represent bottom left corners.
     */
    private char bottomLeftCornerCharacter = DEFAULT_CORNER_CHARACTER;

    /**
     * The character used to represent bottom right corners.
     */
    private char bottomRightCornerCharacter = DEFAULT_CORNER_CHARACTER;

    /**
     * The character used to print the top border.
     */
    private char topBorderCharacter = DEFAULT_HORIZONTAL_BORDER_CHARACTER;

    /**
     * The character used to print the right border.
     */
    private char rightBorderCharacter = DEFAULT_VERTICAL_BORDER_CHARACTER;

    /**
     * The character used to print the bottom border.
     */
    private char bottomBorderCharacter = DEFAULT_HORIZONTAL_BORDER_CHARACTER;

    /**
     * The character used to print the left border.
     */
    private char leftBorderCharacter = DEFAULT_VERTICAL_BORDER_CHARACTER;

    @Override
    public TextSprite print(BinaryTreeNode<T> node) {
        String value = node.getValue().toString();
        String[] lines = value.split("\n");
        int maximumLineLength = getMaximumLineLength(lines);
        int width = 2 + paddingLeft + paddingRight + maximumLineLength;
        int height = 2 + paddingTop + paddingBottom + lines.length;
        TextSprite textSprite = new TextSprite(width, height);
        printCorners(textSprite);
        printBorders(textSprite);
        printLines(textSprite, lines);
        Utils.setEmptyTextSpriteCellsToSpace(textSprite);
        return textSprite;
    }

    public int getTopPadding() {
        return paddingTop;
    }

    public int getRightPadding() {
        return paddingRight;
    }

    public int getBottomPadding() {
        return paddingBottom;
    }

    public int getLeftPadding() {
        return paddingLeft;
    }

    public char getTopLeftCornerCharacter() {
        return topLeftCornerCharacter;
    }

    public char getTopRightCornerCharacter() {
        return topRightCornerCharacter;
    }

    public char getBottomLeftCornerCharacter() {
        return bottomLeftCornerCharacter;
    }

    public char getBottomRightCornerCharacter() {
        return bottomRightCornerCharacter;
    }

    public char getTopBorderCharacter() {
        return topBorderCharacter;
    }

    public char getRightBorderCharacter() {
        return rightBorderCharacter;
    }

    public char getBottomBorderCharacter() {
        return bottomBorderCharacter;
    }

    public char getLeftBorderCharacter() {
        return leftBorderCharacter;
    }

    public void setTopPadding(int paddingTop) {
        this.paddingTop = checkPaddingTop(paddingTop);
    }

    public void setRightPadding(int paddingRight) {
        this.paddingRight = checkPaddingRight(paddingRight);
    }

    public void setBottomPadding(int paddingBottom) {
        this.paddingBottom = checkPaddingBottom(paddingBottom);
    }

    public void setLeftPadding(int paddingLeft) {
        this.paddingLeft = checkPaddingLeft(paddingLeft);
    }

    public void setTopLeftCornerCharacter(char c) {
        topLeftCornerCharacter = c;
    }

    public void setTopRightCornerCharacter(char c) {
        topRightCornerCharacter = c;
    }

    public void setBottomLeftCornerCharacter(char c) {
        bottomLeftCornerCharacter = c;
    }

    public void setBottomRightCornerCharacter(char c) {
        bottomRightCornerCharacter = c;
    }

    public void setTopBorderCharacter(char c) {
        topBorderCharacter = c;
    }

    public void setRightBorderCharacter(char c) {
        rightBorderCharacter = c;
    }

    public void setBottomBorderCharacter(char c) {
        bottomBorderCharacter = c;
    }

    public void setLeftBorderCharacter(char c) {
        leftBorderCharacter = c;
    }

    private int checkPadding(int padding, String errorMessage) {
        if (padding < 0) {
            throw new IllegalArgumentException(
                    errorMessage + ": the given padding is negative: " +
                    padding + ". Must be at least 0!");
        }

        return padding;
    }

    private int checkPaddingTop(int padding) {
        return checkPadding(padding, "Top padding is invalid");
    }

    private int checkPaddingRight(int padding) {
        return  checkPadding(padding, "Right padding is invalid");
    }

    private int checkPaddingBottom(int padding) {
        return checkPadding(padding, "Bottom padding is invalid");
    }

    private int checkPaddingLeft(int padding) {
        return checkPadding(padding, "Left padding is invalid");
    }

    private int getMaximumLineLength(String[] lines) {
        int maximumLineLength = 0;

        for (String line : lines) {
            maximumLineLength = Math.max(maximumLineLength, line.length());
        }

        return maximumLineLength;
    }

    private void printCorners(TextSprite textSprite) {
        int width = textSprite.getWidth();
        int height = textSprite.getHeight();
        textSprite.setChar(0, 0, topLeftCornerCharacter);
        textSprite.setChar(width - 1, 0, topRightCornerCharacter);
        textSprite.setChar(0, height - 1, bottomLeftCornerCharacter);
        textSprite.setChar(width - 1, height - 1, bottomRightCornerCharacter);
    }

    private void printBorders(TextSprite textSprite) {
        int width = textSprite.getWidth();
        int height = textSprite.getHeight();

        for (int x = 1; x < width - 1; ++x) {
            textSprite.setChar(x, 0, topBorderCharacter);
            textSprite.setChar(x, height - 1, bottomBorderCharacter);
        }

        for (int y = 1; y < height - 1; ++y) {
            textSprite.setChar(0, y, leftBorderCharacter);
            textSprite.setChar(width - 1, y, rightBorderCharacter);
        }
    }

    private void printLines(TextSprite textSprite, String[] lines) {
        int startY = 1 + paddingTop;
        int startX = 1 + paddingLeft;

        for (int y = 0; y < lines.length; ++y) {
            char[] chars = lines[y].toCharArray();

            for (int x = 0; x < chars.length; ++x) {
                textSprite.setChar(startX + x, startY + y, chars[x]);
            }
        }
    }
}

DefaultBinaryTreePrinter.java

package net.coderodde.util.tree.support;

import net.coderodde.util.tree.BinaryTreeNode;
import net.coderodde.util.tree.BinaryTreeNodePrinter;
import net.coderodde.util.tree.BinaryTreePrinter;
import net.coderodde.util.tree.TextSprite;

/**
 * Implements a default binary tree printer.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jul 6, 2017)
 * @param <T> the type of the data contained in the binary tree nodes.
 */
public final class DefaultBinaryTreePrinter<T> implements BinaryTreePrinter<T> {

/**
 * When combining the text sprites of two sibling subtrees, by default, at 
 * least one character worth horizontal space will be put between the two
 * sprites.
 */
private static final int DEFAULT_MINIMUM_SIBLING_SPACE = 1;

/**
 * The default character for printing arrow tips.
 */
private static final char DEFAULT_ARROW_TIP_CHARACTER = 'V';

/**
 * The minimum number of spaces between two siblings.
 */
private int siblingSpace = DEFAULT_MINIMUM_SIBLING_SPACE;

/**
 * The arrow tip character.
 */
private char arrowTipCharacter = DEFAULT_ARROW_TIP_CHARACTER;

@Override
public String print(BinaryTreeNode<T> root, 
                    BinaryTreeNodePrinter<T> nodePrinter) {
    if (root == null) {
        return "null";
    }

    TextSprite textSprite = printImpl(root, nodePrinter).textSprite;
    Utils.setEmptyTextSpriteCellsToSpace(textSprite);
    return textSprite.toString();
}

public int getSiblingSpace() {
    return siblingSpace;
}

public char getArrowTipCharacter() {
    return arrowTipCharacter;
}

public void setSiblingSpace(int siblingSpace) {
    this.siblingSpace = checkSiblingSpace(siblingSpace);
}

public void setArrowTipCharacter(char arrowTipCharacter) {
    this.arrowTipCharacter = arrowTipCharacter;
}

private static final class SubtreeDescriptor {

    TextSprite textSprite;
    int rootNodeOffset;
    int rootNodeWidth;
}

private SubtreeDescriptor printImpl(BinaryTreeNode<T> node, 
                                    BinaryTreeNodePrinter<T> nodePrinter) {
    if (node.getLeftChild() == null && node.getRightChild() == null) {
        TextSprite leafNodeTextSprite = nodePrinter.print(node);
        SubtreeDescriptor subtreeDescriptor = new SubtreeDescriptor();
        subtreeDescriptor.rootNodeOffset = 0;
        subtreeDescriptor.rootNodeWidth = leafNodeTextSprite.getWidth();
        subtreeDescriptor.textSprite = leafNodeTextSprite;
        return subtreeDescriptor;
    }

    if (node.getLeftChild() != null && node.getRightChild() != null) {
        return printWithTwoChildrenImpl(node, nodePrinter);
    }

    if (node.getLeftChild() != null) {
        return printWithLeftChildImpl(node, nodePrinter);
    }

    return printWithRightChildImpl(node, nodePrinter);
}

private SubtreeDescriptor printWithTwoChildrenImpl(
        BinaryTreeNode<T> node,
        BinaryTreeNodePrinter<T> nodePrinter) {
    SubtreeDescriptor subtreeDescriptor = new SubtreeDescriptor();
    SubtreeDescriptor leftChildDescriptor = printImpl(node.getLeftChild(),
                                                      nodePrinter);

    SubtreeDescriptor rightChildDescriptor = printImpl(node.getRightChild(),
                                                       nodePrinter);

    TextSprite nodeTextSprite = nodePrinter.print(node);
    TextSprite leftChildTextSprite = leftChildDescriptor.textSprite;
    TextSprite rightChildTextSprite = rightChildDescriptor.textSprite;

    // The height of the resulting text sprite.
    int subtreeTextSpriteHeight = 1 + nodeTextSprite.getHeight() +
            Math.max(leftChildTextSprite.getHeight(), 
                     rightChildTextSprite.getHeight());

    int aLeft = (nodeTextSprite.getWidth() - siblingSpace) / 2;
    int aRight = nodeTextSprite.getWidth() - siblingSpace - aLeft;

    int bLeft = leftChildTextSprite.getWidth() - 
            leftChildDescriptor.rootNodeOffset -
            leftChildDescriptor.rootNodeWidth;

    int leftPartOffset = 0;

    if (aLeft + 2 > bLeft + leftChildDescriptor.rootNodeWidth) {
        leftPartOffset = aLeft + 2 
                               - bLeft 
                               - leftChildDescriptor.rootNodeWidth;
    }

    int rightPartOffset = 0;

    if (rightChildDescriptor.rootNodeOffset +
            rightChildDescriptor.rootNodeWidth < aRight + 2) {
        rightPartOffset = aRight + 2 - rightChildDescriptor.rootNodeOffset
                                     - rightChildDescriptor.rootNodeWidth;
    }

    // The width of the resulting text sprite.
    int subtreeTextSpriteWidth = 
            leftChildTextSprite.getWidth() + 
            leftPartOffset +
            siblingSpace +
            rightPartOffset +
            rightChildTextSprite.getWidth();

    TextSprite subtreeTextSprite = new TextSprite(subtreeTextSpriteWidth, 
                                                  subtreeTextSpriteHeight);

    subtreeTextSprite.apply(nodeTextSprite, 
                            leftChildTextSprite.getWidth() + 
                                    leftPartOffset - aLeft, 0);

    subtreeTextSprite.apply(leftChildTextSprite,
                            0,
                            nodeTextSprite.getHeight() + 1);

    subtreeTextSprite.apply(rightChildTextSprite,
                            leftChildTextSprite.getWidth() + 
                                    leftPartOffset +
                                    siblingSpace +
                                    rightPartOffset,
                            nodeTextSprite.getHeight() + 1);

    int leftArrowLength = Math.max(1,
                                   leftChildTextSprite.getWidth() +
                                   leftPartOffset
                                   - aLeft + 1
                                   - leftChildDescriptor.rootNodeOffset
                                   - leftChildDescriptor.rootNodeWidth / 2);
    int rightArrowLength = Math.max(1,
                            rightPartOffset + 
                            rightChildDescriptor.rootNodeOffset +
                            rightChildDescriptor.rootNodeWidth / 2 - 
                                    aRight);

    int arrowStartX = leftChildTextSprite.getWidth() + leftPartOffset 
                                                     - aLeft;
    int arrowY = nodeTextSprite.getHeight() - 2;

    for (int x = 0; x < leftArrowLength; ++x) {
        subtreeTextSprite.setChar(arrowStartX - x - 1, arrowY, '-');
    }

    subtreeTextSprite.setChar(arrowStartX - leftArrowLength, 
                              arrowY, 
                              '+');

    subtreeTextSprite.setChar(arrowStartX - leftArrowLength,
                              arrowY + 1,
                              '|');

    subtreeTextSprite.setChar(arrowStartX - leftArrowLength,
                              arrowY + 2,
                              arrowTipCharacter);

    arrowStartX = leftChildTextSprite.getWidth()
                        + leftPartOffset 
                        - aLeft
                        + nodeTextSprite.getWidth();

    for (int x = 0; x < rightArrowLength; ++x) {
        subtreeTextSprite.setChar(arrowStartX + x, arrowY, '-');
    }

    subtreeTextSprite.setChar(arrowStartX + rightArrowLength, arrowY, '+');
    subtreeTextSprite.setChar(arrowStartX + rightArrowLength, 
                              arrowY + 1,
                              '|');

    subtreeTextSprite.setChar(arrowStartX + rightArrowLength, 
                              arrowY + 2, 
                              arrowTipCharacter);

    subtreeDescriptor.rootNodeOffset = leftChildTextSprite.getWidth() 
            + leftPartOffset
            - aLeft;

    subtreeDescriptor.rootNodeWidth = nodeTextSprite.getWidth();
    subtreeDescriptor.textSprite = subtreeTextSprite;
    return subtreeDescriptor;
}

private SubtreeDescriptor printWithLeftChildImpl(
        BinaryTreeNode<T> node,
        BinaryTreeNodePrinter<T> nodePrinter) {
    SubtreeDescriptor subtreeDescriptor = new SubtreeDescriptor();
    SubtreeDescriptor leftChildDescriptor = printImpl(node.getLeftChild(),
                                                      nodePrinter);

    TextSprite nodeTextSprite = nodePrinter.print(node);
    TextSprite leftChildTextSprite = leftChildDescriptor.textSprite;

    // The height of the resulting text sprite.
    int subtreeTextSpriteHeight = 1 + nodeTextSprite.getHeight()
                                    + leftChildTextSprite.getHeight();

    int a = (nodeTextSprite.getWidth() - siblingSpace) / 2;

    int b = leftChildDescriptor.textSprite.getWidth() 
            - leftChildDescriptor.rootNodeOffset
            - leftChildDescriptor.rootNodeWidth;

    int leftPartOffset = 0;

    if (a + 2 > b  + leftChildDescriptor.rootNodeWidth) {
        leftPartOffset = a + 2 - b - leftChildDescriptor.rootNodeWidth;
    }

    // The width of the resulting text sprite.
    int subtreeTextSpriteWidth =
            leftChildTextSprite.getWidth() + 
            leftPartOffset + 
            nodeTextSprite.getWidth() - 
            a;

    TextSprite subtreeTextSprite = new TextSprite(subtreeTextSpriteWidth,
                                                  subtreeTextSpriteHeight);
    subtreeTextSprite.apply(nodeTextSprite,
                            leftChildDescriptor.textSprite.getWidth() + 
                                    leftPartOffset - a,
                            0);

    subtreeTextSprite.apply(leftChildTextSprite, 
                            0, 
                            nodeTextSprite.getHeight() + 1);

    int arrowLength = Math.max(1, leftChildTextSprite.getWidth() + 
                                  leftPartOffset 
                                  - a + 1
                                  - leftChildDescriptor.rootNodeOffset 
                                  - leftChildDescriptor.rootNodeWidth / 2);

    int arrowStartX = leftChildDescriptor.textSprite.getWidth() 
                        + leftPartOffset - a;

    int arrowY = nodeTextSprite.getHeight() - 2;

    for (int x = 0; x < arrowLength; ++x) {
        subtreeTextSprite.setChar(arrowStartX - x - 1, arrowY, '-');
    }

    subtreeTextSprite.setChar(arrowStartX - arrowLength, arrowY, '+');
    subtreeTextSprite.setChar(arrowStartX - arrowLength, arrowY + 1, '|');
    subtreeTextSprite.setChar(arrowStartX - arrowLength, arrowY + 2, '|');

    subtreeDescriptor.rootNodeOffset = leftChildTextSprite.getWidth() 
                                     + leftPartOffset - a;
    subtreeDescriptor.rootNodeWidth = nodeTextSprite.getWidth();
    subtreeDescriptor.textSprite = subtreeTextSprite;
    return subtreeDescriptor;
}

private SubtreeDescriptor printWithRightChildImpl(
        BinaryTreeNode<T> node,
        BinaryTreeNodePrinter<T> nodePrinter) {
    SubtreeDescriptor subtreeDescriptor = new SubtreeDescriptor();
    SubtreeDescriptor rightChildDescriptor = printImpl(node.getRightChild(),
                                                       nodePrinter);

    TextSprite nodeTextSprite = nodePrinter.print(node);
    TextSprite rightChildTextSprite = rightChildDescriptor.textSprite;

    // The height of the resulting text sprite.
    int subtreeTextSpriteHeight = 1 + nodeTextSprite.getHeight()
                                    + rightChildTextSprite.getHeight();

    // Number of spaces on the right side of the sibling separator.
    int a = (nodeTextSprite.getWidth() - siblingSpace) / 2;

    int rightPartOffset = 0;

    if (rightChildDescriptor.rootNodeOffset + 
            rightChildDescriptor.rootNodeWidth < a + 2) {
        rightPartOffset = a + 2 - rightChildDescriptor.rootNodeOffset -
                                  rightChildDescriptor.rootNodeWidth;
    }

    // The width of the resulting text sprite.
    int subtreeTextSpriteWidth = 
            nodeTextSprite.getWidth() 
            - a
            + rightPartOffset
            + rightChildTextSprite.getWidth();

    TextSprite subtreeTextSprite = new TextSprite(subtreeTextSpriteWidth, 
                                                  subtreeTextSpriteHeight);
    subtreeTextSprite.apply(nodeTextSprite, 0, 0);
    subtreeTextSprite.apply(rightChildTextSprite,
                            nodeTextSprite.getWidth() - a + rightPartOffset,
                            1 + nodeTextSprite.getHeight());

    int arrowLength = Math.max(1, 
                               rightPartOffset + 
                               rightChildDescriptor.rootNodeOffset +
                               rightChildDescriptor.rootNodeWidth / 2 - a);

    int arrowStartX = nodeTextSprite.getWidth();
    int arrowY = nodeTextSprite.getHeight() - 2;

    for (int x = 0; x < arrowLength; ++x) {
        subtreeTextSprite.setChar(arrowStartX + x, arrowY, '-');
    }

    subtreeTextSprite.setChar(arrowStartX + arrowLength, arrowY, '+');
    subtreeTextSprite.setChar(arrowStartX + arrowLength, arrowY + 1, '|');
    subtreeTextSprite.setChar(arrowStartX + arrowLength, arrowY + 2, '|');

    subtreeDescriptor.rootNodeOffset = 0;
    subtreeDescriptor.rootNodeWidth = nodeTextSprite.getWidth();
    subtreeDescriptor.textSprite = subtreeTextSprite;
    return subtreeDescriptor;
}

private int checkSiblingSpace(int siblingSpace) {
    if (siblingSpace < 0) {
        throw new IllegalArgumentException("Sibling space is negative: " +
                siblingSpace);
    }

    return siblingSpace;
}

}

You can find the entire project containing a funky demo program here: https://github.com/coderodde/BinaryTreePrinter

Using it, you may get something like:

                             +----+                    
          +------------------|1000|-----+              
          |                  +----+     |              
          |                             |              
         +---+                       +----+            
 +-------|123|-----------+         +-|1673|---------+  
 |       +---+           |         | +----+         |  
 |                       |         |                |  
+--+                   +---+     +----+          +----+
|52|----+        +-----|147|-+   |1450|        +-|2017|
+--+    |        |     +---+ |   +----+        | +----+
        |        |           |                 |       
      +--+      +---+     +---+              +----+    
    +-|67|   +--|130|-+   |157|            +-|2000|    
    | +--+   |  +---+ |   +---+            | +----+    
    |        |        |                    |           
   +--+     +---+  +---+                 +----+        
   |60|     |127|  |141|                 |1988|        
   +--+     +---+  +---+                 +----+       

Critique request

Please tell me anything that comes to mind.

\$\endgroup\$
  • 2
    \$\begingroup\$ I think I would put the boxes (like the 1000 box) in the center of the line. \$\endgroup\$ – RobAu Jul 8 '17 at 10:56
  • \$\begingroup\$ @RobAu That's a good one. \$\endgroup\$ – coderodde Jul 8 '17 at 10:58
  • \$\begingroup\$ For an ordered tree it is actually nicer the way it is now since all numbers are sorted left to right. Then again centered would look great as well (I think) so it thumbed up Rob's comment :) \$\endgroup\$ – Imus Jul 10 '17 at 8:40
1
\$\begingroup\$

Basically, I would say - installing SonarQube project and running it agains your code to see violations. Generally - long methods. Probably they do more than one thing. return "null", separate string and numbers could be "static final String NULL".

private int checkPaddingTop(int padding) {
    return checkPadding(padding, "Top padding is invalid");
}

private int checkPaddingRight(int padding) {
    return  checkPadding(padding, "Right padding is invalid");
}

private int checkPaddingBottom(int padding) {
    return checkPadding(padding, "Bottom padding is invalid");
}

private int checkPaddingLeft(int padding) {
    return checkPadding(padding, "Left padding is invalid");
}

Seems like copy/paste code - could use use enum for Bottom/Left/Right/Top and use as input argument and have same code?

private SubtreeDescriptor printImpl(BinaryTreeNode<T> node, 
                                BinaryTreeNodePrinter<T> nodePrinter) {
if (node.getLeftChild() == null && node.getRightChild() == null) {
    TextSprite leafNodeTextSprite = nodePrinter.print(node);
    SubtreeDescriptor subtreeDescriptor = new SubtreeDescriptor();
    subtreeDescriptor.rootNodeOffset = 0;
    subtreeDescriptor.rootNodeWidth = leafNodeTextSprite.getWidth();
    subtreeDescriptor.textSprite = leafNodeTextSprite;
    return subtreeDescriptor;
}

constructing and initializing should be done probably in some factory class. Not in method named print.

Well and unit testing. When you try to unit test different scenarios for your code to make sure it works as expected - you will see how unit tests shape your code design. Its very hard to unit test method that does 20 things, so you will step by step refactor it to have one thing done and test its different cases/outcomes.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.