postordercomparator.java

postordercomparator.java

//Implementar un método que determine si los valores almacenados en el árbol según un recorrido postorder se encuentran ordenados de menor a mayor (según el criterio de un 
//comparador recibido por parámetro).
//(es sobre un árbol binario)

public class BinaryTree<T> {

	private Node<T> root;

	private class Node<T> {
		private Node<T> left;
		private Node<T> right;
		private T elem;
	}

	public boolean isPostOrdered(Comparator<T> c) {

		return isPostOrdered(root, null, c) != null;
	}

	private Node<T> isPostOrdered(Node<T> n, Node<T> previous, Comparator<T> c) {

		if (n.left == null && n.right == null) {
			if (previous != null) {
				if (c.compare(previous.elem, n.elem) >= 0) {
					return null;
				}
			}
			return n;
		}


		if (n.left != null) {
			previous = isPostOrdered(n.left, previous, c);
			if (previous == null) {
				return null;
			}
		}

		if (n.right != null) {
			previous = isPostOrdered(n.right, previous, c);
			if (previous == null) {
				return null;
			}
		}

		if (c.compare(previous.elem, n.elem) >= 0) {
			return null;
		}

		return n;
	}
}

//          10
//      7       8
//    1   5   2   6