DEV Community

Andrew Lee
Andrew Lee

Posted on

Binary Search Tree: Insert, Find, and Validate

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;
  }
}
Enter fullscreen mode Exit fullscreen mode

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;
    }
  }
}

Enter fullscreen mode Exit fullscreen mode

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;
  }
}

Enter fullscreen mode Exit fullscreen mode

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;
}

Enter fullscreen mode Exit fullscreen mode

Top comments (1)

Collapse
 
kalium profile image
kalium.xyz

Keep up the good work c: