Validates a Binary Search Tree (version 4)

validatetreev4.js

// Validates a binary tree.
// This is a much elegant implementation than the previous two
// since it does not store an array of all the values, but rather 
// it just keeps track of the last element compared against. 
// Also, notice how processing is stopped as soon as a bad
// element is found.  
function isValidTree(root) {

  var lastValue = null;
  var validator = function(value) {

    if(lastValue != null && value < lastValue) {
      // Value is less than previous lastValue. 
      // We are done, this is a bad tree.
      return false;
    }

    lastValue = value;
    return true;
  };

  return walkNode(root, validator);
}


function walkNode(node, validateNode) {

  if(node == null) return true;

  return walkNode(node.left, validateNode) && 
    validateNode(node.value) && 
    walkNode(node.right, validateNode);

};


////////////////////////////////
// Samples start here
////////////////////////////////

// valid tree
var sample1 = {
  value: 10,
  left: {value: 5, left: null, right: null},
  right: {value: 15, left: null, right: null}
};

// invalid tree
var sample2 = {
  value: 10,
  left: {value: 14, left: null, right: null},
  right: {value: 15, left: null, right: null}
};

// valid tree
var sample3 = {
  value: 10,
  left: {value: 5, left: {value: 2, left: null}, right: {value: 6, left: null, right: null}},
  right: {value: 15, left: {value: 13, left: null}, right: {value: 20, left: null, right: null}}
};

// invalid tree
var sample4 = {
  value: 10,
  left: {value: 54, left: {value: 2, left: null}, right: {value: 6, left: null, right: null}},
  right: {value: 15, left: {value: 13, left: null}, right: {value: 20, left: null, right: null}}
};

// invalid tree
var sample5 = {
  value: 10,
  left: {value: 5, left: {value: 1, left: null, right: null }, right: {value: 6, left: null, right: null}},
  right: {value: 15, left: {value: 4, left: null, right: null}, right: {value: 20, left: null, right: null}}
};

console.log("Sample1 - valid? ", isValidTree(sample1));
console.log("Sample2 - valid? ", isValidTree(sample2));
console.log("Sample3 - valid? ", isValidTree(sample3));
console.log("Sample4 - valid? ", isValidTree(sample4));
console.log("Sample5 - valid? ", isValidTree(sample5));