Following the secret marriage, Juliet's cousin Tybalt sends a challenge to Romeo. Romeo refuses to fight, which angers his friend, Mercutio, who then fights with Tybalt. Mercutio is accidentally killed as Romeo intervenes to stop the fight. In anger, Romeo pursues Tybalt, kills him, and is banished by the prince.
Juliet is anxious when she learns of these happenings. Friar Laurence arranges for Romeo to spend the night with Juliet before he leaves for Mantua. Meanwhile, Lord Capulet retaliates by re-scheduling Juliet and Count Paris' marriage to the next day. Juliet's parents are angry when Juliet doesn't want to marry Paris, but they don't know about her secret marriage to Romeo.
Count Paris loves the idea of getting married the next day to Juliet, but Juliet is having none of it -- he's gross. As they check in to a nearby inn, Paris asks for one room for the two of them. Juliet counters back, saying she wants her own separate room. The innkeeper, trying to be as unbiased as possible, says he'll award the room arrangements to the one who can solve the following problem:
100 people are at a party. The people who didn’t know each other shook hands. There will always be 2 who know each other out of any 3. What is the largest number of handshakes that occur at the party?
Juliet solves the problem, so they sleep in separate rooms.
Count Paris is excited about his impending marriage to Juliet, so he naturally spends his night planning their future. How can he ensure a contingency plan for every outcome of their sure-to-be fruitful and illustrious matrimony?
The class constructor should accept (at least) a single argument which will represent the value for its root node. Each instance should have two methods: insert, which takes a numerical value and returns a new binary search tree containing that value, and contains, which takes a numerical value and returns true or false based on whether the tree contains it.
The existing binary search tree shall not be mutated by insert. That is:
const bstA = new ImmutableBST(5);
const bstB = bstA.insert(6);
console.log(bstA); // contains only 5, NOT 6
console.log(bstB); // contains 5 and 6Follow-up: build a remove method, which takes a value and returns a new binary search tree that does not include that value.
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.
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// O(1) creation time
class ImmutableBST {
constructor(value, left, right) {
this.value = value; // Set value to given argument.
this.left = left || null; // Set left to either given argument OR null.
this.right = right || null; // Set right to either given argument OR null.
this.size = 1 + ((left && left.size) || 0) + ((right && right.size) || 0);
// 1 (to count this node) then add left.size (if exists) and right side (if exists)
// otherwise, in both cases, we add zero
}
// O(log n) insertion time
insert(value) {
const newValue = this.value; // Grab value from the constructor.
let newLeft, newRight;
if (value <= this.value) {
// If value to insert is less than constructor value...
// We will not change the right value because we are traversing down the left branch.
newRight = this.right; // Clone the right node of the inserted right value.
// If left node exists, recurse until no left value exists.
// If no left exists, create a new IBST with value to insert.
newLeft = this.left ? this.left.insert(value) : new ImmutableBST(value);
} else {
// If value to insert is greater than constructor value...
// We will not change the left value because we are traversing down the right branch.
newLeft = this.left; // Clone the left node of the inserted left value.
// If right node exists, recurse until no right value exists.
// If no right exists, create a new IBST with value to insert.
newRight = this.right
? this.right.insert(value)
: new ImmutableBST(value);
}
// Clone this 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);
}
// O(log n) retrieval time
contains(value) {
if (this.value === value) return true;
if (value < this.value) {
// If this.left exists, recurse down the left branch until you find the value, else return false.
return Boolean(this.left) && this.left.contains(value);
} else {
// If this.right exists, recurse down the right branch until you find the value, else return false.
return Boolean(this.right) && this.right.contains(value);
}
}
// Min & Max are utility functions for remove.
min() {
if (!this.left) return this.value;
// If this is the final value (min value) of the left branch, return.
else return this.left.min(); // Else, recurse until final value is found.
}
max() {
if (!this.right) return this.value;
// If this is the final value (max value) of the right branch, return.
else return this.right.max(); // Else, recurse until final value is found.
}
// O(log n) removal time
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;
// In that case, we will remove a value from the "fuller" branch.
// Then we will use that value as the value for our new node.
if (this.left.size > this.right.size) { // If left is greater than right...
// Get the largest value of the smaller child (right).
newRight = this.right;
// Get the largest value from the larger child (left).
newValue = this.left.max();
// Recurse to reorganize the tree.
newLeft = this.left.remove(newValue);
} else { // If right is greater than left...
// Get the largest value of the smaller child (left).
newLeft = this.left;
// Get the largest value from the larger child (right).
newValue = this.right.min();
// Recurse to reorganize the tree.
newRight = this.right.remove(newValue);
}
return new ImmutableBST(newValue, newLeft, newRight); // Return the new tree.
} else if (!this.left && !this.right) {
// Case 2: The node has no children...
// EASY! If a node has no children, its parent should replace the value 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 {
// HOWEVER, if we have not yet found the given value to remove, continue recursing...
const newValue = this.value;
let newLeft, newRight;
if (value < this.value) { // If value given is less than this.value...
newRight = this.right;
// Clone the left node with the value removed,
// or if there is no left node, stop recursing.
newLeft = this.left ? this.left.remove(value) : null;
} else { // If value given is greater than this.value...
newLeft = this.left;
// Clone the right node with the value removed,
// or if there is no right node, stop recursing.
newRight = this.right ? this.right.remove(value) : null;
}
// Finally, clone this 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);
}
}
}
let myBSTBase = new ImmutableBST(5) // contains 5
let myBSTBase2 = myBSTBase.insert(10) // contains 5, 10
let myBSTBase3 = myBSTBase.insert(15).insert(7) // contains 5, 15, 7
let buildingOnABase = myBSTBase3.insert(12) // contains 5, 15, 7, 12