Question about binary tree min and height

[pbotsaris]

Hello everyone,

I have been following the data structure course and I notice in lesson 12(find tree min) the base case

`if(root.leftNode == null && root.rightNode == null)
    return root.value;

does not stop the recursion from attempting to read a null pointer in root.value

 private int min(Node root){
      //  if(root == null)
      //       will get a nullpointer exception without this base case?

        if(root.leftNode == null && root.rightNode == null)
           return root.value;

            int left =  min(root.leftNode);
            int right =  min(root.rightNode);

            return Math.min(Math.min(left, right), root.value);

    }

What am I missing here?

[alex.cisija]

Is your tree’s root a null value? Did you add any values to the tree before running the function?

[pbotsaris]

Hey Alex,

The tree contains values. My point is that the base case in the course:

   if(root.leftNode == null && root.rightNode == null)
           return root.value;

Does not stop the program from trying to read from a null pointer unless the tree is completely synemtrical.

The base below worked for me:

 if(root == null)
  // a number greater than root.value;
     return Integer.MAX_VALUE;

[alex.cisija]

You mean like, when there’s a right child but no left child?
I’m going through the same course right now so sorry if I’m not so helpful

I remember also having trouble with Mosh’s base case. (IsLeaf() method)

Good to know your other base case works.

[tabRobert]

Hi, It looks like there is a bug. I realized it now on lesson 11. There we have the same base case which works just fine with the given example, but if we choose another tree that has no the same level order (left/right) we will get the same exception. It works fine with this new check you added.

In my case I did it in the same if condition.

if (root == null || root.LeftChild == null && root.RightChild == null)
            {
                return 0;
            }

[pbotsaris]

Look good! you can omit the {} if you want

[tabRobert]

Yes, I can. In our company, we decided to use them always because in this way we will avoid bugs and actually, we have just few ifs with just one line of code inside.

[jmrunkle]

If the tree is empty (root is null) then there is no meaning for finding the min so it should throw an exception in my opinion. If you return any value it is impossible to distinguish between that value actually being the minimum and the empty case.

[adddy]

hey man i encountered the same problem

so this happens when your tree is not complete i.e

something like this ,

what would happen is that when the recursion reaches node with the value(12) it would not take into account that the right leaf is empty because of statement .

------------------- if(root.leftNode == null && root.rightNode == null)

here we check if both of them are empty , and only then return the root.value .

hence the compiler would try to run
-------------------int right = min(root.rightNode);
this and it would give a null pointer exception .

–SOLUTION–

private int min(Node root){

                //condition          //if condition true    //if it is false
    var m1 = (root.leftChild!=null) ? min(root.leftChild) : root.value;

    var m2 = (root.rightChild!=null) ? min(root.rightChild) : root.value;

    return Math.min(Math.min(m1,m2), root.value);
}

hope this helps.

[jmrunkle]

I think using Integer.MAX_VALUE is the best option, you just have to separate the recursive case from the root case so you can treat it differently.

public int min() {
  if (isEmpty()) {
    throw new EmptyTreeException(
      "cannot find min of empty tree");
  }
  return min(root);
}

public boolean isEmpty() {
  return root == null;
}

private int min(Node current) {
  if (current == null) {
    return Integer.MAX_VALUE;
  }
  return IntStream.of(
      current.value,
      min(current.leftNode),
      min(current.rightNode))
    .min()
    .getAsInt();
}

Where EmptyTreeException is just a subclass of IllegalStateException (so clients get a better error to catch if necessary).

[rakshith]

Simple solution, hope this helps

// Method to find minimum value
  public int findMin() {
      if (rootNode == null)
          throw new IllegalStateException();
  
      return findMin(rootNode);
  }

// Private recursive method
private int findMin(Node root) {
    //If a node is a leaf node, i.e it doesn't have either a left or right child
    if (isLeaf(root))
        return root.value;

    //If a node does not have left child but has right child
    if (root.leftChild == null)
        return Math.min(root.rightChild.value, root.value);

    //If a node does not have right child but has left child
    if (root.rightChild == null)
        return Math.min(root.leftChild.value, root.value);

    //If a node is a parent node, i.e it has both left and right children
    return Math.min(root.value,
                    Math.min(findMin(root.leftChild), 
                             findMin(root.rightChild)));
}

// Method to check if a node is a leaf node
private boolean isLeaf(Node root) {
    return root.leftChild == null && root.rightChild == null;
}

[Parker13]

The Binary Tree base case in the code you provided is incorrect and you are correct that it will result in a null pointer exception. The correct base case should be:

if(root == null)
    return Integer.MAX_VALUE;

This will ensure that the function returns Integer.MAX_VALUE if the root node is null, thus avoiding the null pointer exception.

[Utkarsh]

This wont work if you have a binary search tree in the order of fashion 1 , - 10 , -20 , -30
This will return -10 in the second if condition

[rakshith]

If the tree looks like this, then the solution is correct!!
I’m getting -30 as the final output

[Utkarsh]

A binary search tree would be of the fashion where all childs would be in left only as per the example

[Roman]

In your case, this 2 if statements returning child values instead of keep diving till the leaf:

//If a node does not have left child but has right child
if (root.leftChild == null)
    return Math.min(root.rightChild.value, root.value);

//If a node does not have right child but has left child
if (root.rightChild == null)
    return Math.min(root.leftChild.value, root.value);

You may have node with only right child, which not necessary will be a leaf.
here is an approach I used to solve this issue:

private int min(Node root) {
    int right = 0;
    int left = 0;

    if (isLeaf(root)) {
        return root.value;
    }
    else if (root.leftChild == null)
        right = left = min(root.rightChild);
    else if (root.rightChild == null)
        right = left = min(root.leftChild);
    else {
        left = min(root.leftChild);
        right = min(root.rightChild);
    }

    return Math.min(Math.min(left,right), root.value);
}