Looking for a sanity check on validating binary search trees

Data Structures
1

I’m not sure if this is an error by @Mosh or my understanding is flawed. In Mosh’s solution for validating binary search trees (lecture 16 of Binary Trees topic in The Ultimate Data Structures & Algorithms: Part 2) I see two issues. Code copied for clarity:

public boolean isBinarySearchTree() {
  return isBinarySearchTree(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}

private boolean isBinarySearchTree(Node root, int min, int max) {
  if (root == null)
    return true;

  if (root.value < min || root.value > max)
    return false;

  return
    isBinarySearchTree(root.leftChild, min, root.value - 1)
    && isBinarySearchTree(root.rightChild, root.value + 1, max);
}

First, if you store Integer.MAX_VALUE or Integer.MIN_VALUE in your tree it will fail the check implemented in isBinarySearchTree() even if it otherwise follows the rules for placement of the nodes. I know this is an obscure edge case, but writing a validation function that would reject a perfectly valid tree just seems off to me.

Second, in the recursion calls for the left and right children, he is adding (and subtracting) 1 from the passed min and max values. However, in the comparison operations he is using strictly less than (<) and strictly greater than (>). By doing this, it would reject adjacent numbers that would be perfectly acceptable node values. For example if your root.value is 20 and its rightChild.value is 21 (perfectly acceptable in a binary search tree) it will fail the next recursion step because he is saying isBinarySearchTree(root.rightChild, 21, Integer.MAX_VALUE) when inspecting the right hand tree which fails when the next round checks 21 < 21.

Maybe he got his thinking mixed up and was trying to address my first point, but forgot to change the comparison line to if (root.value <= min || root.value >= max). Then adding (or subtracting) 1 would make sense to allow the full range of Integer.MIN_VALUE to Integer.MAX_VALUE and prevent duplicate nodes.

As it stands now, this method does not properly validate binary search trees and flags perfectly acceptable structures as false.

Am I reading this wrong?

2

The second part, I came here to ask the same thing.

image

Specifically these highlighted parts. I don’t understand why the subtracting/adding is necessary.
Are both of us forgetting something?

This is how I ended up doing it:


private boolean validateBinary(int min, int max, Node root){
        if(root == null) return true;
        return (min <= root.value && root.value <= max) &&
                validateBinary(min, root.value, root.leftChild) &&
                validateBinary(root.value, max, root.rightChild);
    }

Let me know if you found out why he did it that way? :confused:

3

Why would that cause it to fail? It seems to me it should be fine. You cannot have anything less or greater than those values.

4

Let’s step through the case. So let’s do the simplest case: root 1 with right child 2.

We start with recursive call passing root (which is 1), MIN, and MAX.

This passes and we get to the recursion. Left passes because it is null so we get to the and condition for the right child (2) passing the following arguments: root.rightChild (2), root.value+1 (1+1=2), and MAX.

Skipping the null check, we check if root.value (2) is less than min (2) - so 2 < 2 which is false - so we proceed to the right condition of the or which is root.value (2) is greater than max (MAX) - so 2 > MAX which is also false - so the whole expression is false. Therefore we do not enter that code block which would return false. Ultimately that recourses to the empty left and right children which will return true.

This works exactly correctly. If the limit were set to root.value rather than adding/subtracting 1 it would technically allow a tree with the same value in there twice. Walk that through yourself if you need convincing.

Tldr: Mosh’s code is correct.

5

Vikeman is right. If the root node is Integer.MAX_VALUE, root.value +1 would fail. Additional check for these are needed.