// File: BinaryTree.java
// Binary Tree
// Copyright (C) 2008 Gregory D. Weber
// Revised 2008 Oct 28, Oct 31
// Goal is to reduce the "dual" methods to single static methods.
// Treat the empty binary tree as null, and get rid of the Tnode class.
// First problem: static methods cannot return a parameterized type,
// even though the type parameter occurs in their arguments.  :-(
// So let's drop type parameters.

// Copyright (C) 2006 Gregory D. Weber

/** binary trees with element type E */

public class BinaryTree<E> {

    // Fields -- may be public, since they are immutable

    private final E _item;
    private final BinaryTree<E> _left, _right;

    // Constructor

    public BinaryTree (E item, BinaryTree<E> left, BinaryTree<E> right) {
	_item = item;
	_left = left;
	_right = right;
    }

    // Accessors

    public E root () { return _item; }
    public BinaryTree<E> left () { return _left; }
    public BinaryTree<E> right () { return _right; }

    // Equals

    public boolean equals (Object obj) {
	return ((obj instanceof BinaryTree) &&
		equals((BinaryTree) obj));
    }

    protected boolean equals (BinaryTree other) {
	return ((this == other) ||
		(root().equals(other.root()) &&
		 left().equals(other.left()) &&
		 right().equals(other.right())));
    }

    // toString

    /** Stringify the empty tree as "".
	For non-empty trees, something like
	
            / Right
	 Root
	    \ Left
    */

    public String toString () {
	return string(this);
    }

    public static String string (BinaryTree tree) {
	return string("", "", tree);
    }

    public static String string (String indent, String prefix, BinaryTree tree)
    {
	if (tree == null)
	    return "";
	else {

	    // Increase indentation by string length of root + 3
	    String rootstr1 = tree._item.toString();
	    String newindent = indent + spaces(rootstr1.length() + 3);

	    // Reverse inorder traversal
	    String rightstr = string(newindent, "/ ", tree._right);
	    String rootstr = indent + prefix + rootstr1;
	    String leftstr = string(newindent, "\\ ", tree._left);
	    return rightstr + rootstr + "\n" + leftstr;
	}
    }

    protected static String spaces (int n) {
	String result = "";
	for (int i = 0; i < n; i++)
	    result += " ";
	return result;
    }



}