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;
}
Top comments (1)
Keep up the good work c: