## 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.

 ``````1 2 3 4 5 6 7 8 `````` `````` 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:

 ``````1 2 3 4 5 `````` ``````class TreeNode { TreeNode left; TreeNode right; int value; } ``````

## The solution in Java code

Option 1:

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 `````` ``````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:

 ``````1 2 3 4 5 6 7 8 9 `````` ``````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:

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 `````` ``````import java.util.LinkedList; import java.util.Queue; public class FindMaxValueInTree { static int findMax(TreeNode root) { Queue queue = new LinkedList<>(); int max = Integer.MIN_VALUE; queue.add(root); while (!queue.isEmpty()) { TreeNode treenode = queue.poll(); if (treenode.value > max) max = treenode.value; if (treenode.left != null) queue.add(treenode.left); if (treenode.right != null) queue.add(treenode.right); } return max; } } ``````

## Test cases to validate our solution

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 `````` ``````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)); } } ``````