Binary Search Tree: Insert, Find, and Validate

Andrew Lee - Mar 2 '20 -

Trees can have nodes that can have unlimited number of children of any value. Binary search tree is a tree data structure with more constraints.

Constraints

Every node can have at most two children
Node to left needs to have value less than parent
Node to right needs to have value greater than parent

Binary Tree

Binary search tree is not the same as a Binary tree. Binary trees have nodes that can have at most two children, but there is no restriction on its left value being less than the parent or the right value being more than the parent.

Node

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

Insert

class Node {
  // ...

  insert(data) {
    const newNode = new Node(data);
    const isLeft = newNode.value < this.data;

    if (this.left && isLeft) {
      return this.left.insert(data);
    }

    if (this.right && !isLeft) {
      return this.right.insert(data);
    }

    if (isLeft) {
      this.left = newNode;
    } else {
      this.right = newNode;
    }
  }
}

Find

class Node {
  // ...

  find(data) {
    const isLeft = data < this.data;

    if (data === this.data) {
      return this;
    }

    if (this.left && isLeft) {
      return this.left.find(data);
    }

    if (this.right && !isLeft) {
      return this.right.find(data);
    }

    return null;
  }
}

Validate

function validateBST(node, min = null, max = null) {
  if (max && node.data > max) {
    return false;
  }

  if (min && node.data < min) {
    return false;
  }

  if (node.left) {
    return validateBST(node.left, min, node.value);
  }

  if (node.right) {
    return validateBST(node.right, node.value, max);
  }

  return true;
}