Good evening! 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:

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.

Given the following tree node definition:

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?

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)

Try to solve this here or in Interactive Mode.

How do I practice this challenge?

xxxxxxxxxx

    '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

Here's our guided, illustrated walk-through.

How do I use this guide?