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:

  1. The left sub-tree of a node has a value less than or equal to its parent node's value.
  2. The right sub-tree of a node has a value greater than to its parent node's value.
Description

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)
JAVASCRIPT
OUTPUT
Results will appear here.