REACTO_Immutable-BST.md

Prompt

Create an immutable binary search tree class ImmutableBST:

• Feel free to use either a classic constructor function or ES6 class approach
• The constructor should accept (at least) a single argument which will represent the value for its root node
• Each instance should have two methods:
  1. insert, which takes a numerical value and returns a new binary search tree containing that value
  2. contains, which takes a numerical value and returns true or false based on whether the tree contains it

insert should NOT mutate the existing binary search tree. For example:

const bstA = new ImmutableBST(5);
const bstB = bstA.insert(6);
console.log(bstA); // contains only 5, NOT 6
console.log(bstB); // contains 5 and 6

Extra Credit: If time allows, implement a remove method, which takes a value and returns a new binary search tree that does not include that value.

Examples

const bst = new ImmutableBST(5);
const bstMore = bst.insert(4).insert(3).insert(1).insert(10).insert(11).insert(15).insert(2).insert(100);
bstMore.contains(5); // true
bstMore.contains(3); // true
bstMore.contains(11); // true
bstMore.contains(12); // false
console.log(bst === bstMore); // false, because of immutability

Solution (ES6 Class)

class ImmutableBST {
  constructor(value, left, right){
    this.value = value;
    this.left = left || null;
    this.right = right || null;
    this.size = 1 + (left && left.size || 0) + (right && right.size || 0);
  }

// Insert Method (this is different from a regular BST - must create copies)
  insert (value) {
    const newValue = this.value; // clone root node in order to return a totally new bst (see return statement below)
    let newLeft, newRight;
    // recursively search for position in which to add the new node
    if (value < this.value) {
      newLeft = (this.left ? this.left.insert(value) : new ImmutableBST(value));
      newRight = this.right; // clone right node 
    } else {
      newRight = (this.right ? this.right.insert(value) : new ImmutableBST(value));
      newLeft = this.left; // clone left node 
    }
    // clone root node with the same value and either a new left child or a new right child (depending on above)
    return new ImmutableBST(newValue, newLeft, newRight);
  };

// Contains Method (same as for a regular BST)
  contains (value) {
    if (this.value === value) return true;
    if (value < this.value) { 
      // check to left if there is a value on the left, if not return false
      return Boolean(this.left) && this.left.contains(value);
    } else { 
      // check to the right if there is a value on the right, if not return false
      return Boolean(this.right) && this.right.contains(value);
    }
  };

// Helper Functions for Remove
  min () {
    if (!this.left) return this.value;
    else return this.left.min();
  };
  max () {
    if (!this.right) return this.value;
    else return this.right.max();
  };

// Remove Method
  remove (value) {
    if (this.value === value) {
      // if we have matched, distinguish between three different cases
      if (this.left && this.right) { // case 1: the node has both children
        let newValue, newLeft, newRight;
        // remove a value from the child w/ higher number of size
        // we will use that value as the value for our new node
        if (this.left.size > this.right.size) {
          newRight = this.right;
          // get the largest of the smaller child
          newValue = this.left.max();
          newLeft = this.left.remove(newValue);
        } else {
          newLeft = this.left;
          // get the smallest of the larger child
          newValue = this.right.min();
          newRight = this.right.remove(newValue);
        }
        return new ImmutableBST(newValue, newLeft, newRight);
      } 
      else if (!this.left && !this.right) { // case 2: the node has no children
        // easy, if a node has no children its parent should replace it with null
        return null;
      } else { // case 3: the node has one child
        // also easy, if a node has one child, its parent should replace it with that child
        return this.left || this.right;
      }
    } else { // we have not yet found the given value to remove, continue recursing
      const newValue = this.value; // clone root
      let newLeft, newRight;
      if (value < this.value) {
        newLeft = (this.left ? this.left.insert(value) : new ImmutableBST(value));
        newRight = this.right; // clone right node 
      } else {
        newRight = (this.right ? this.right.insert(value) : new ImmutableBST(value));
        newLeft = this.left; // clone left node 
      }
      // clone root node with the same value and either a new left child or a new right child (depending on above)
      return new ImmutableBST(newValue, newLeft, newRight);
    }
  };
}

Solution (Constructor Function)

function ImmutableBST (value, left, right) {
  this.value = value;
  this.left = left || null;
  this.right = right || null;
  this.size = 1 + (left && left.size || 0) + (right && right.size || 0);
}

ImmutableBST.prototype.insert = function (value) {
  const newValue = this.value;
  let newLeft, newRight;
  if (value <= this.value) {
    newRight = this.right;
    newLeft = (this.left ? this.left.insert(value) : new ImmutableBST(value));
  } else {
    newLeft = this.left;
    newRight = (this.right ? this.right.insert(value) : new ImmutableBST(value));
  }
  return new ImmutableBST(newValue, newLeft, newRight);
};

ImmutableBST.prototype.contains = function (value) {
  if (this.value === value) return true;
  if (value < this.value) {
    return Boolean(this.left) && this.left.contains(value);
  } else {
    return Boolean(this.right) && this.right.contains(value);
  }
};

ImmutableBST.prototype.min = function () {
  if (!this.left) return this.value;
  else return this.left.min();
};

ImmutableBST.prototype.max = function () {
  if (!this.right) return this.value;
  else return this.right.max();
};

ImmutableBST.prototype.remove = function (value) {
  if (this.value === value) {
    if (this.left && this.right) { 
      let newValue, newLeft, newRight;
      if (this.left.size > this.right.size) {
        newRight = this.right;
        newValue = this.left.max();
        newLeft = this.left.remove(newValue);
      } else {
        newLeft = this.left;
        newValue = this.right.min();
        newRight = this.right.remove(newValue);
      }
      return new ImmutableBST(newValue, newLeft, newRight);
    } else if (!this.left && !this.right) { 
      return null;
    } else { 
      return this.left || this.right;
    }
  } else {
    const newValue = this.value;
    let newLeft, newRight;
    if (value < this.value) {
      newRight = this.right;
      newLeft = (this.left ? this.left.remove(value) : null);
    } else {
      newLeft = this.left;
      newRight = (this.right ? this.right.remove(value) : null);
    }
    return new ImmutableBST(newValue, newLeft, newRight);
  }
};

Read more here: https://en.wikipedia.org/wiki/Persistent_data_structure#Trees and/or here: https://medium.com/@dtinth/immutable-js-persistent-data-structures-and-structural-sharing-6d163fbd73d2#.7xy1ccvr0.