Question about the execution of a BST JS recursive function

Question

I came up with a solution for a BST validation problem. I'll lay out the problem and the code I wrote first, and then tell u which part of the execution i don't understand.

// --- Directions
/* Given a node, validate the binary search tree,
   ensuring that every node's left hand child is
   less than the parent node's value, and that
   every node's right hand child is greater than
   the parent. e.g.:
 
   10
 5   15
0     20 
 999    
        */

class Node {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }

  insert(data) {
    if (data < this.data && this.left) {
      this.left.insert(data);
    } else if (data < this.data) {
      this.left = new Node(data);
    } else if (data > this.data && this.right) {
      this.right.insert(data);
    } else if (data > this.data) {
      this.right = new Node(data);
    }
  }
}

function validate(node, min = null, max = null) {
  if (node.right) {
    min = node.data;
    if (node.right && node.right.data > min) {
      return validate(node.right, min, max);
    } else if (node.right && node.right.data < min) {
      return false;
    }
  }
  if (node.left) {
    max = node.data;
    if (node.left && node.left.data < max) {
      return validate(node.left, min, max);
    } else if (node.left && node.left.data > max) {
      return false;
    }
  }
  return true;
}

const n = new Node(10);
n.insert(5);
n.insert(15);
n.insert(0);
n.insert(20);
n.left.left.left = new Node(999);

console.log(validate(n));

What I was expecting would happen was that the function would validate the rights side of the tree first, and then start working on the left side. What happens though is that once it checks the right side, it just returns true from the recursive calls. It goes back up to the initial value of n, but doesn't check the second if statement for the left side of the tree, it just exits the function.

I'm assuming it might exit because the initial function call ends up returning true from recursing over the first if statement so then it doesn't bother checking the second one. If that's the case, is there a way to make the function check the second if statement as well, and not exit the function after the first one?

Answer 1

Indeed, the first part of your code (if node.right is truthy) will always execute a return, so there is no way that then also the second part of your code would get executed.

It is OK to return when the result is false, but in the other case, you should not return yet:

function validate(node, min = null, max = null) {
  if (node.right) {
    min = node.data;
    if (node.right && node.right.data > min) {
      if (!validate(node.right, min, max)) return false; // <---
    } else if (node.right && node.right.data < min) {
      return false;
    }
  }
  if (node.left) {
    max = node.data;
    if (node.left && node.left.data < max) {
      return validate(node.left, min, max);
    } else if (node.left && node.left.data > max) {
      return false;
    }
  }
  return true;
}

I just modified what is necessary for your problem, but there are lots of checks in your code that are duplicating what was already asserted. For instance, there is no need to check that node.right is truthy again when you are in the first if block. So you could reduce the code to this:

function validate(node, min = null, max = null) {
  if (node.right && (node.right.data < node.data || 
        !validate(node.right, node.data, max))) return false;
  if (node.left && (node.left.data > node.data ||
        !validate(node.left, min, node.data))) return false;
  return true;
}

...and this could be even more reduce to just one return statement, but that I'll leave for you ,-)