Wednesday, February 21, 2024
HomeSoftware EngineeringFind out how to Discover the Max Tree Node Worth in Java

Find out how to Discover the Max Tree Node Worth in Java


The problem

You’re given a binary tree. Implement the tactic findMax which returns the maximal node worth within the tree.

For instance, the utmost within the following Tree is 11.

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

Observe:

  • Tree node values vary is Integer MIN VALUE – Integer MAX VALUE constants.
  • Tree can unbalanced and unsorted.
  • Root node is all the time not null.

You’re given a tree node class as follows:

class TreeNode {
  TreeNode  left;
  TreeNode  proper;
  int worth;
}

The answer in Java code

Possibility 1:

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

Possibility 2:

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

Possibility 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);
      whereas (!queue.isEmpty()) {
        TreeNode treenode = queue.ballot();
        if (treenode.worth > max) max = treenode.worth;
        if (treenode.left != null) queue.add(treenode.left);
        if (treenode.proper != null) queue.add(treenode.proper);
      }
      return max;
    }
}

Check circumstances to validate our resolution

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

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Most Popular

Recent Comments