Implement a Binary Search Tree (Medium)
Good evening! Here's our prompt for today.
You may see this problem at Instacart, Pinterest, Adobe, Oracle, Lyft, Netflix, Ebay, Groupon, Snap, Splunk, Tableau Software, Yelp, Pivotal, Spotify, Citadel, Hudson River-trading, Glassdoor, Servicetitan, Appdirect, and Amplitude.
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)
xxxxxxxxxx
69
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;
}
OUTPUT
Results will appear here.