sarahzhao25

BinarySearchTree.prototype.height = function(treeNode) {
  return (treeNode === null) ? -1 : Math.max(this.height(treeNode.left), this.height(treeNode.right)) + 1;
};

sarahzhao25

checkAndRotateRoots(root) {
  if (root) {
    let x = root.balanceFactor();
    if (x > 1 || x < -1) rotate(root);
    checkAndRotateRoots(root.parent.node);
  }
}

sarahzhao25

function rightRotate(root) {
  let pivot = root.left;
  if (pivot.right) {
    //establish right to be child of root's parent.
    pivot.right.parent.node = root;
    pivot.right.parent.side = 'left';
  }
  root.left = pivot.right;
  pivot.parent.node = root.parent.node;
  (root.parent.node) ? root.parent.node[root.parent.side] = pivot: pivot.parent.side = '';

sarahzhao25

function rotate(root) {
  if (root.balanceFactor() > 1) {
    if (root.left.balanceFactor() === -1) leftRotate(root.left);
    rightRotate(root);
  }
  else if (root.balanceFactor() < -1) {
    if (root.right.balanceFactor() === 1) rightRotate(root.right);
    leftRotate(root);
  }
 }

sarahzhao25

function BinarySearchTree(value) {
  this.value = value;
  this.left = this.right = null;
  this.parent = {node: null, side: ‘’};
}

sarahzhao25

BinarySearchTree.prototype.balanceFactor = function() {
  return this.height(this.left) - this.height(this.right);
}

sarahzhao25

//ROOT Tree:
{
  this.value = 15;
  this.left = BST(10);
  this.right = null;
  this.parent = {node: BST(20), side: 'left'};
}
//root.height() => 2;
//root.balanceFactor() => 2;

sarahzhao25

//ROOT Tree (rotated to RIGHT):
{
  this.value = 15;
  this.left = null;
  this.right = null;
  this.parent = {node: BST(10), side: 'right'};
}
//root.height() => 0;
//root.balanceFactor() => 0;

sarahzhao25

NOTE: This was taken from Cracking the Coding Interview 6th Edition.

Prompt

You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1's digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.

Example

Input: (7 -> 1 -> 6) + (5 -> 9 -> 2). That is, 617 + 295. Output: (2 -> 1 -> 9). That is, 912.

Solution

sarahzhao25

K-Messed Array Sort

See Repl

Prompt

Given an array of integers arr where each element is at most k places away from its sorted position, write a function sortKMessedArray that sorts arr.

Example

For an input array of size 10 and k = 2, an element belonging to index 6 in the sorted array will be located at either index 4, 5, 6, 7 or 8 in the input array.