Question about binary tree min and height

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?

1 Like

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

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;
1 Like

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 :sweat_smile:

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

Good to know your other base case works.

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

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

Yes, I can. :slight_smile: 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.

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.

hey man i encountered the same problem

so this happens when your tree is not complete i.e
image
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.

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

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