Maximum element in a binary tree

Question

This method finds the maximum in a binary tree. I have used generics to make this code more usable. However, I am not sure if I have written efficient and good Java code.

This is a method inside a class using generics and implementing Comparable interface for the generic parameter E.

private E maximumElement(TreeNode<E> root, E parentValue) {
  E max;
  if(root==null)
        max=parentValue;
  else {
    max = root.element;
    E leftMax = maximumElement(root.left, max);
    E rightMax = maximumElement(root.right, max);
    if(rightMax.compareTo(max) > 0)
              max = rightMax;
    if(leftMax.compareTo(max) > 0)
              max = leftMax;
   }
   return max;
}

Answer 1

static, and possibly public

I'd recommend having this method outside your binary tree class itself. It can operate on a binary tree, but it's not a method that requires to be specified directly inside the binary tree. Also, it doesn't use any state other than what is passed through its parameters. As such, I would make it static and probably also public.

First call

It's currently a bit weird to call this method from the start, the parentValue parameter is used for further recursions, but what value should it be passed originally? Considering this problem, I'd separate this method into a public part and a private part, such as:

public static <E extends Comparable<E>> E maximumElement(TreeNode<E> root) {
     return maximumElement(root, root.element);
}

private static <E extends Comparable<E>> E maximumElement(TreeNode<E> root, E parentValue) {
     ...
}

General stuff

• It's good practice to always use braces. It improves readability and reduces the risk of bugs.
• Using early returns helps reduce indentation and makes it more apparent how special cases are handled (otherwise you have to scroll down to make sure that the value isn't changed)

Rewritten version with some additional formatting improvements:

private static <E extends Comparable<E>> E maximumElement(TreeNode<E> root, E parentValue) {
    if (root == null) {
        return parentValue;
    }
    E max = root.element;
    E leftMax = maximumElement(root.left, max);
    E rightMax = maximumElement(root.right, max);
    if (rightMax.compareTo(max) > 0) {
        max = rightMax;
    }
    if (leftMax.compareTo(max) > 0) {
        max = leftMax;
    }
    return max;
}

If you want to remove the parentValue parameter, you would need to introduce a null check:

public static <E extends Comparable<E>> E maximumElement(TreeNode<E> root) {
    if (root == null) {
        throw new IllegalArgumentException("root cannot be null");
    }
    E max = root.element;
    if (root.left != null) {
        E leftMax = maximumElement(root.left);
        if (leftMax.compareTo(max) > 0) {
            max = leftMax;
        }
    }
    if (root.right != null) {
        E rightMax = maximumElement(root.right);
        if (rightMax.compareTo(max) > 0) {
            max = rightMax;
        }
    }
    return max;
}

This repeated != null checks and everything inside can be extracted to a method

private static <E extends Comparable<E>> E maxMaximum(E current, TreeNode<E> other) {
    if (other != null) {
        E otherMax = maximumElement(other);
        if (otherMax.compareTo(current) > 0) {
            return otherMax;
        }
    }
    return current;
}

Which leads to:

public static <E extends Comparable<E>> E maximumElement(TreeNode<E> root) {
    if (root == null) {
        throw new IllegalArgumentException("root cannot be null");
    }
    E max = root.element;
    max = maxMaximum(max, root.left);
    max = maxMaximum(max, root.right);
    return max;
}