Mark As Completed Discussion

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:

  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)

Try to solve this here or in Interactive Mode.

How do I practice this challenge?

PYTHON
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment

Here's our guided, illustrated walk-through.

How do I use this guide?

Access all course materials today

The rest of this tutorial's contents are only available for premium members. Please explore your options at the link below.

Returning members can login to stop seeing this.