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<TreeNode> 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));
    }
}