treeAlgorithms/Algorithms.java

Go to the documentation of this file.

package treeAlgorithms;

public class Algorithms {

    public interface NodeVisitor<T extends Comparable<T>> {
        void visit(TreeNode<T> node);
    } // interface NodeVistor

    private Algorithms() {
    }

    public static <T extends Comparable<T>> boolean isOrdered(TreeNode<T> root) {
        boolean ordered = false;
        if (root != null) {
            ordered = true;
            if (root.getLeft() != null) {
                boolean orderedBranch = isOrdered(root.getLeft());
                if (!orderedBranch) {
                    ordered = false;
                }
            }
            if (root.getRight() != null) {
                boolean orderedBranch = isOrdered(root.getRight());
                if (!orderedBranch) {
                    ordered = false;
                }
            }
            if (ordered) {
                Comparable<T> rootVal = root.getValue();
                if (root.getLeft() != null) {
                    @SuppressWarnings("unchecked")
                    T leftVal = (T) root.getLeft().getValue();
                    if (rootVal.compareTo(leftVal) < 0) {
                        ordered = false;
                    }
                }
                if (root.getRight() != null) {
                    @SuppressWarnings("unchecked")
                    T rightVal = (T) root.getRight().getValue();
                    if (rootVal.compareTo(rightVal) > 0) {
                        ordered = false;
                    }
                }
            }
        }
        return ordered;
    }

    public static <T extends Comparable<T>> void inOrder(TreeNode<T> root, NodeVisitor<T> visitor) {
        if (root != null) {
            inOrder(root.getLeft(), visitor);
            visitor.visit(root);
            inOrder(root.getRight(), visitor);
        }
    } // inOrder

}