Validates a Binary Search Tree (version 2)

validtreev2.js

function isValidTree(root) {
  
  // Walk the tree in order and add values to an array.
  var values = [];
  walkNode(root, values);

  if (values.length == 1) {
    // one-node tree is valid
    return true;
  }

  // Make sure values in array are in fact in order
  var i;
  var valid = true;
  for(i=0; i<values.length-1; i++) {
    if (values[i] > values[i+1]) {
      valid = false;
      break;
    }
  }
  console.dir(values);
  return valid;
}


function walkNode(node, values) {

  if(node != null) {
    walkNode(node.left, values);
    values.push(node.value);
    walkNode(node.right, values);
  }

};


////////////////////////////////
// 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));