Skip to content

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; }
Code language: Java (java)

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; } }
Code language: Java (java)

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 ); } }
Code language: Java (java)

Option 3:

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; } }
Code language: Java (java)

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)); } }
Code language: Java (java)

See also  How to Create a Hashtag Generator in Python
Tags:
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x