AlgoDaily - Implement a Binary Search Tree

Implement a Binary Search Tree (Medium)

Good morning! 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 and 1000000000
Expected time complexity for most BST operations (including search, insert, and delete) is O(log n) where n being the number of nodes
Expected space complexity : O(n)

xxxxxxxxxx
​
 
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.