BinaryTree class with extra methods

Question

I am taking a data structures course. I would like to check whether my BinaryTree code is perfect, fine or has lots of mistakes.

I would like any kind of advice on this code so I can learn from my mistakes (syntax, techniques, style, etc...).

Note: This is not a binary search tree.

BinaryTree class:

/**
 *  @uniersity  Saint Joseph's University
 *  @college    College of Arts and Sciences
 *  @department Computer Science
 *  @course     CSC 550: Object Oriented Design & Data Structures
 */

package mih1406.csc550.trees;
import java.io.Serializable;

// To make life easier...
// <E extends Integer> to simplify it if any method requires Integer
// eg: getSum, countLessThan
public class BinaryTree<E extends Integer> implements Serializable {
    // Inner Class
    protected class Node<E extends Integer> implements Serializable {
        protected E data;
        protected Node<E> left;
        protected Node<E> right;

        public Node(E data) {
            this.data = data;

            left = null;
            right = null;
        }

        public String toString() {
            return data.toString();
        }
    }

    // Data Fields
    protected Node<E> root;

    // Constructors
    public BinaryTree() {
        root = null;
    }

    protected BinaryTree(Node<E> root) {
        this.root = root;
    }

    public BinaryTree(E data, BinaryTree<E> leftTree,
                                      BinaryTree<E> rightTree) {
        root = new Node(data);
        if(leftTree == null || leftTree.root == null)
            root.left = null;
        else
            root.left = leftTree.root;

        if(rightTree == null || rightTree.root == null)
            root.right = null;
        else
            root.right = rightTree.root;
    }

    // Methods
    public BinaryTree<E> getLeftSubtree() {
        if(root == null)
            return new BinaryTree<E>(null);
        else
            return new BinaryTree<E>(root.left);
    }

    public BinaryTree<E> getRightSubtree() {
        if(root == null)
            return new BinaryTree<E>(null);
        else
            return new BinaryTree<E>(root.right);
    }

    public E getData() {
        if(root == null)
            return null;
        else
            return root.data;
    }

    public boolean isLeaf() {
        if(root == null)
            return false;
        else {
            if(root.left == null && root.right == null)
                return true;
            else
                return false;
        }
    }

    public String toString() {
        StringBuilder sb = new StringBuilder();

        sb.append("Pre-Order Traversal:\n");
        preOrderTraversal(root, 1, sb);
        sb.append("\n");

        sb.append("In-Order Traversal:\n");
        inOrderTraversal(root, 1, sb);
        sb.append("\n");

        sb.append("Post-Order Traversal:\n");
        postOrderTraversal(root, 1, sb);

        return sb.toString();
    }

    private void preOrderTraversal(Node<E> node, int depth,
                                             StringBuilder sb) {
        for(int i = 1; i < depth; i++)
            sb.append(".");

        if(node == null) {
            sb.append("null\n");
            return;
        }

        sb.append(node.data);
        sb.append("\n");
        preOrderTraversal(node.left, depth + 1, sb);
        preOrderTraversal(node.right, depth + 1, sb);
    }

    private void inOrderTraversal(Node<E> node, int depth,
                                             StringBuilder sb) {
        if(node == null) {
            for(int i = 1; i < depth; i++)
                sb.append(".");

            sb.append("null\n");
            return;
        } else {
            inOrderTraversal(node.left, depth + 1, sb);
            for(int i = 1; i < depth; i++)
                sb.append(".");

            sb.append(node.data);
            sb.append("\n");
            inOrderTraversal(node.right, depth + 1, sb);
        }
    }

    private void postOrderTraversal(Node<E> node, int depth,
                                             StringBuilder sb) {
        if(node == null) {
            for(int i = 1; i < depth; i++)
                sb.append(".");

            sb.append("null\n");
            return;
        } else {
            postOrderTraversal(node.left, depth + 1, sb);
            postOrderTraversal(node.right, depth + 1, sb);
            for(int i = 1; i < depth; i++)
                sb.append(".");

            sb.append(node.data);
            sb.append("\n");
        }
    }

    // Gets the height of the tree
    public int getHeight() {
        return getHeight(root);
    }

    private int getHeight(Node<E> node) {
        if(node == null)
            return 0;
        else {
            int L = getHeight(node.left);
            int R = getHeight(node.right);

            return Math.max(L, R) + 1;
        }
    }

    // Gets the sum of all nodes in the tree
    public int getSum() {
        return getSum(root);
    }

    private int getSum(Node<E> node) {
        if(node == null)
            return 0;

        int S = node.data;
        int L = getSum(node.left);
        int R = getSum(node.right);

        return S + L + R;
    }

    // Counts how many items less than the given target
    public int countLessThan(E target) {
        return countLessThan(root, target);
    }

    private int countLessThan(Node<E> node, E target) {
        if(node == null)
            return 0;
        else {
            int S = (node.data < target) ? 1 : 0;
            // or int S = (node.data.compareTo(target) < 0) ? 1 : 0;
            int L = countLessThan(node.left, target);
            int R = countLessThan(node.right, target);

            return S + L + R;
        }
    }

    public static void main(String[] args) {
        //Tests goes here of course :)
    }

    // The following methods *should* produce the same
    // result as their identically named ones with the class
    // BinaryTree, but they cannot access nodes directly

    // Gets the sum of all nodes in the tree
    public static int getSum(BinaryTree<Integer> T) {
        if(T.getData() == null)
            return 0;

        int S = T.getData();
        int L = getSum(T.getLeftSubtree());
        int R = getSum(T.getRightSubtree());

        return S + L + R;
    }

    // Counts how many items less than the given target
    public static int countLessThan(BinaryTree<Integer> T, int target) {
        if(T == null || T.getData() == null)
            return 0;
        else {
            int S = (T.getData() < target) ? 1 : 0;
            // or int S = (T.getData().compareTo(target) < 0) ? 1 : 0;
            int L = countLessThan(T.getLeftSubtree(), target);
            int R = countLessThan(T.getRightSubtree(), target);

            return S + L + R;
        }
    }
}

Answer 1

This is a good start. Here's what I have to say about it.

• There really is no point in making E constrained on Integer. The Integer class is final so it can't be anything but an Integer. Either remove that constraint or remove the use of generics here and make it an Integer.

• Your inner class could be made static. A node here doesn't need the outer class to mean anything and can exist on its own.

• Pretty much all members in your classes that are protected probably should be private. Don't get into the habit of using protected over private just because. Only do it because you intend for it to be overridden or used in a derived class.

• Personally, I wouldn't allow for the possibility of having a null root node. It will help simplify your code so you don't have to put null checks everywhere you need to operate on the root.

• Your toString() method should return a string representation of a single tree. What you have there (and in other related methods) is the kind of code I would expect to see in a "printTree" method. It doesn't belong there.

• Consider making your different traversal methods either return an iterator that iterates over the nodes in the appropriate order or use them to apply the visitor pattern on what operations you want to do on your tree. It would make them more useful in general rather than just only for filling a string buffer.

• Local variables should be in camelCase at most, not Capitalized.

Answer 2

Your code has the trees be mostly immutable, which is a good idea, but to be more elegant, you should

1. Make all fields final.

2. Use null for leaves, and change the Node constructor to take the data and left and right.

3. isLeaf should be true just for root=null, and all accessors on leaves should (implicitly or explicitly) throw a NPE.

4. As previous commentators have said: get rid of useless generics (best, get rid of extends Integer), implement real iterators for traversals and fix toString. You can then write sum using an iterator.

5. Write equals(Object) and hashCode().