Software Engineering

# How to Find the Max Tree Node Value in Java

## The challenge#

You are given a binary tree. Implement the method `findMax` which returns the maximal node value in the tree.

For example, the maximum in the following Tree is 11.

``````              7
/   \
/     \
5       2
\       \
6        11
/\      /
1  9   4
``````

Note:

• Tree node values range is Integer MIN VALUE – Integer MAX VALUE constants.
• Tree can unbalanced and unsorted.
• Root node is always not null.

You are given a tree node class as follows:

``````class TreeNode {
TreeNode  left;
TreeNode  right;
int value;
}
``````

## The solution in Java code#

Option 1:

``````public class FindMaxValueInTree {
static int findMax(TreeNode  root) {
int numMax = root.value;
if(root.left != null) {
numMax = Math.max(numMax, findMax(root.left));
}
if(root.right != null) {
numMax = Math.max(numMax, findMax(root.right));
}
return numMax;
}
}
``````

Option 2:

``````public class FindMaxValueInTree {
static int findMax(TreeNode root) {
return
Math.max(
root.left != null ? Math.max(root.value, findMax(root.left)) : root.value,
root.right != null ? Math.max(root.value, findMax(root.right)) : root.value
);
}
}
``````

Option 3:

``````import java.util.LinkedList;
import java.util.Queue;
public class FindMaxValueInTree {
static int findMax(TreeNode  root) {
int max = Integer.MIN_VALUE;
while (!queue.isEmpty()) {
TreeNode treenode = queue.poll();
if (treenode.value > max) max = treenode.value;
}
return max;
}
}
``````

## Test cases to validate our solution#

``````import org.junit.Test;
import static org.hamcrest.CoreMatchers.*;
import static org.junit.Assert.assertThat;
public class FindMaxValueInTreeTest {
@Test
public void findMaxInLeaf() {
TreeNode root = TreeNode.leaf(-1);
assertThat(FindMaxValueInTree.findMax(root), is(-1));
}
@Test
public void findMaxInOneChildTree() {
TreeNode root = TreeNode.leaf(1).withLeftLeaf(2);
assertThat(FindMaxValueInTree.findMax(root), is(2));
}
@Test
public void findMaxInPerfectTree() {
TreeNode left = TreeNode.leaf(-22).withLeaves(9, 50);
TreeNode right = TreeNode.leaf(11).withLeaves(9, 2);
TreeNode root = TreeNode.join(5, left, right);
assertThat(FindMaxValueInTree.findMax(root), is(50));
}
@Test
public void findMaxInUnbalancedTree() {
TreeNode left = TreeNode.leaf(50).withLeaves(-100, -10);
TreeNode right = TreeNode.leaf(40);
TreeNode root = TreeNode.join(6, left, right);
assertThat(FindMaxValueInTree.findMax(root), is(50));
}
@Test
public void findMaxInNegativeTree() {
TreeNode left = TreeNode.leaf(-50).withLeaves(-100, -10);
TreeNode right = TreeNode.leaf(-40);
TreeNode root = TreeNode.join(-600, left, right);
assertThat(FindMaxValueInTree.findMax(root), is(-10));
}
}
``````