JavaScript; validateBinaryTree function gives value error on node

Question

A coding challenge in which we are to write a function that determines if a binary tree is valid. The tree is simply a collection of BinaryTreeNodes that are manually linked together. The validateBinaryTree function should return false if any values on the left subtree are greater than the root value or false if any values on the right subtree are less, and true otherwise.

Here is the BinaryTreeNode class:

class BinaryTreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }

  insertLeft(value) {
    this.left = new BinaryTreeNode(value);
    return this.left;
  }

  insertRight(value) {
    this.right = new BinaryTreeNode(value);
    return this.right;
  }

  depth_first_print() {
    console.log(this.value);
    if (this.left) {
      this.left.depth_first_print();
    }
    if (this.right) {
      this.right.depth_first_print();
    }
  }

}

Here is the validateBinaryTree function:

const validateBinaryTree = (rootNode) => {
  const rootValue = rootNode.value;
  let isValid = true;
  const validateLeft = (node) => {
    if (node.value > rootValue) isValid = false;
    if (node.left) {
      validateLeft(node.left);
    }
    if (node.right) {
      validateLeft(node.right);
    }
  }
  const validateRight = (node) => {
    if (node.value < rootValue) isValid = false;
    if (node.left) {
      validateRight(node.left);
    }
    if (node.right) {
      validateRight(node.right);
    }
  }
  validateLeft(rootNode.left);
  validateRight(rootNode.right);
  return isValid;
}


//Build an invalid binary tree which will look like this:
//    10
//   /
//  50

const tree = new BinaryTreeNode(10);
tree.insertLeft(50);

The following function call should print false to the console:

console.log(validateBinaryTree(tree));

But instead I get the following error:

if (node.value < rootValue) isValid = false;
             ^

TypeError: Cannot read property 'value' of null

raina77ow · Accepted Answer · 2019-02-20 20:16:36Z

Your initial code fails because you try to invoke validateRight on rootNode.right, which is null. That's why it's actually better to place that check (against node === null case) inside validator itself.

Also I'd simplify this code by passing two separate functions inside - one for the left branch, another for the right - closured upon rootNode value. For example:

const validateBinaryTree = (rootNode) => {
  const forLeft  = val => val < rootNode.value;
  const forRight = val => val > rootNode.value;

  const validateBranch = (node, branchComparator) => {
    return node === null || 
      branchComparator(node.value) &&
      validateBranch(node.left, branchComparator) && 
      validateBranch(node.right, branchComparator);
  }

  return validateBranch(rootNode.left, forLeft) && validateBranch(rootNode.right, forRight);
}

This version also has a (slight) benefit of immediately stopping the check whenever failing node has been found (because of short-circuit nature of && operator in JS).

Collectives™ on Stack Overflow

JavaScript; validateBinaryTree function gives value error on node

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related