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

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

``````