Good morning! Here's our prompt for today.
Let's implement a Binary Search Tree
! Recall that a binary search tree
, or a BST
, is a binary tree
that is ordered via these two properties:
- The left sub-tree of a node has a value less than or equal to its parent node's value.
- The right sub-tree of a node has a value greater than to its parent node's value.

Given the following tree node definition:
JAVASCRIPT
1class Node {
2 constructor(val) {
3 this.val = val;
4 this.left = null;
5 this.right = null;
6 }
7}
Can you fill out the skeleton code and implement a binary search
tree with #add
and #remove
methods?
JAVASCRIPT
1class BST {
2 constructor(val) {
3 this.root = new Node(val);
4 }
5
6 add(val) {
7 // fill this in
8 }
9
10 remove(val) {
11 // fill this in
12 }
13}
Constraints
- Maximum number of nodes <=
1000
- Value of each node can lie between
-1000000000
and1000000000
- Expected time complexity for most BST operations (including search, insert, and delete) is
O(log n)
wheren
being the number of nodes - Expected space complexity :
O(n)
Try to solve this here or in Interactive Mode.
How do I practice this challenge?
xxxxxxxxxx
69
'PASSED: ' + 'const bst = new BST(4);bst.add(3);bst.add(5);bst.remove(3);'
var assert = require('assert');
​
class BST {
constructor(val) {
this.root = new Node(val);
}
​
add(val) {
// fill this in
}
​
remove(val) {
// fill this in
}
}
​
// const bst = new BST(4);
// bst.add(3);
// bst.add(5);
// console.log(bst.root.left.val === 3);
// console.log(bst.root.right.val === 5);
​
function Node(val) {
this.val = val;
this.left = null;
this.right = null;
}
​
// Regular binary trees
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment
We'll now take you through what you need to know.
How do I use this guide?