treesSolutions.js

/**
 *
 * (1) isBST
 * Go down the tree, comparing the value of the left and right nodes to root node.
 * Then call a recursive function that narrows:
 * - the maximum value for left tree
 * - the minimum value for the right tree
 * A tree is BST if
 * - the current value is within those limitations
 * - the left node is less than the current value
 * - the right node is greater than the current value
 * If a subtree is not a BST, then the current tree is not a BST as well
 */

function helper(tree, min, max) {
  if (!tree) return true;
  if (tree.left && tree.left.value < min) return false;
  if (tree.right && tree.right.value > max) {
    return false;
  }
  const left = helper(tree.left, min, Math.min(tree.value, max));
  const right = helper(tree.right, Math.max(tree.value, min), max);
  if (!left || !right) {
    return false;
  }
  return true;
}

function isBST(tree) {
  const min = -Infinity;
  const max = Infinity;
  return helper(tree, min, max);
}
/**
 * (2) Merge two BST's
 * 1. Use in-order traversal to get turn the tree into a sorted array of smallest value to greatest value
 *    - Alternatively you could use a LinkedList instead of an array.
 *    - Both options are presented below for comparison
 *    - We use an iterative version of the in-order traversal to save on memory.
 *    - You can use a recursive solution to get to the coded solution faster and redo it using iterative later.
 * 2. Then merge the two sorted arries / linked lists into one large sorted array / linked list
 * 3. Then turn the sorted array / linked list into a balanced BST
 *
 * Balancing tree algorithm:
 * 1. Get the middle of the array and make it the root
 * 2. Recursively do the same for the left half and right half
 *     - Get the middle of the left half and make it the left child of the root created in 1
 *     - Do above for right
 */

// TreeNode structure
class TreeNode {
  constructor({ value, left, right }) {
    this.value = right;
    this.left = left;
    this.right = right;
  }
}

// Creating test data
const nodeTwo = new TreeNode({ value: 2 });
const nodeFour = new TreeNode({ value: 4 });
const nodeThree = new TreeNode({ left: nodeTwo, right: nodeFour, value: 3 });
const nodeSix = new TreeNode({ value: 6 });
const treeOne = new TreeNode({ left: nodeThree, right: nodeSix, value: 5 });
const nodeOne = new TreeNode({ value: 1 });
const treeTwo = new TreeNode({ value: 7, left: nodeOne });
//     tree
//    5      7
//  3  6    1
// 2 4

/**
 * Converting a BST into a sorted array.
 * O(N) runtime where N = number of nodes in BST
 */
function bstToSortedArray(tree) {
  // if no tree passed in, return;
  if (!tree) return;
  // Create sorted array
  const sortedArray = [];
  // Create stack
  const stack = [];
  // Start at root node;
  let currentNode = tree;
  // If there are no nodes left, we're done.
  while (stack.length || !currentNode) {
    if (currentNode) {
      stack.push(currentNode);
      currentNode = currentNode.left;
    } else {
      // There are no left nodes.
      // Get the last node on top of tack
      currentNode = stack.pop();
      sortedArray.push(currentNode);
      currentNode = currentNode.right;
    }
  }
  return sortedArray;
}

class LinkedListNode {
  constructor({ value, next }) {
    this.value = value;
    this.next = next;
  }
}

function bstToLinkedList(tree) {
  // if no tree passed in, return;
  if (!tree) return;
  // Create linked list head
  const linkedList = null;
  // Create stack
  const stack = [];
  // Create pointer for current node
  let currentLinkedListNode = null;
  // Start at root node;
  let currentNode = tree;
  // If there are no nodes left, we're done.
  while (stack.length || !currentNode) {
    if (currentNode) {
      stack.push(currentNode);
      currentNode = currentNode.left;
    } else {
      // There are no left nodes.
      // Get the last node on top of tack
      currentNode = stack.pop();
      // create Linked List Node from current value
      const nextNode = new LinkedListNode({
        value: currentNode.value,
        next: null,
      });
      // If there is no linked list, create one, and set it as the current linked list node
      if (!linkedList) {
        linkedList = nextNode;
        currentLinkedListNode = nextNode;
      } else {
        // Create attach next node to current linked list node
        currentLinkedListNode.next = nextNode;
        // set current linked list node to next node;
        currentLinkedListNode = currentLinkedListNode.next;
      }
    }
  }
  return linkedList;
}

/**
 * Merges two arrays in JS
 * O(M+N) runtime where M is the number of elements in array one
 * and N is the number of elements in array two
 *
 * There are repetitive logic in this function, so you can move them to smaller utility functions
 */
function mergeTwoArrays(arrOne, arrTwo) {
  const mergedArray = [];
  // Initialize pointers to know where in the array we are
  // If we are optimizing for space, use a linked list instead of an array
  let arrOnePointer = 0;
  let arrTwoPointer = 0;
  while (arrOne.length || arrTwo.length) {
    // If there are no element left in first array, push the rest of the second array
    if (!arrOne[arrOnePointer] && arrOne[arrOnePointer] !== 0) {
      while (arrTwo[arrTwoPointer]) {
        const value = arrTwo[arrTwoPointer];
        mergedArray.push(value);
        arrTwoPointer++;
      }
    }
    // If there are no element left in second array, push the rest of the first array
    if (!arrTwo[arrTwoPointer] && arrTwo[arrTwoPointer] !== 0) {
      while (arrOne[arrOnePointer]) {
        const value = arrTwo[arrTwoPointer];
        mergedArray.push(value);
        arrTwoPointer++;
      }
    }
    // If there are valid values where the pointers are
    if (arrOne[arrOnePointer] && arrTwo[arrTwoPointer]) {
      // if the first array pointer is less than the second array pointer
      if (arrOne[arrOnePointer] <= arrTwo[arrTwoPointer]) {
        // Get the value at the pointer
        const value = arrOne[arrOnePointer];
        // Push it into mergedArray
        mergedArray.push(value);
        // Increment pointer
        arrOnePointer++;
      }
      // if the first array pointer is greater than the second array pointer
      if (arrOne[arrOnePointer] > arrTwo[arrTwoPointer]) {
        // Get the value at the second pointer
        const value = arrTwo[arrTwoPointer];
        // Push it into mergedArray
        mergedArray.push(value);
        // Increment second pointer
        arrTwoPointer++;
      }
    }
  }
  return mergedArray;
}

function mergeTwoLinkedLists(linkedListOne, linkedListTwo) {
  // if there are no linked list one, return linked list two
  if (!linkedListOne) return linkedListTwo;
  // if there are no linked list two, return linked list one
  if (!linkedListTwo) return linkedListOne;
  // Set head of linkedListOne to currentNodeOne
  const currentNodeOne = linkedListOne;
  // Set head of linkedListTwo to currentNodeTwo
  const currentNodeTwo = linkedListTwo;
  // Create initial mergedLinkedList, set it to the lowest current node value, and increment that linked list
  const mergedLinkedList = null;
  if (currentNodeOne.value <= currentNodeTwo.value) {
    mergedLinkedList = currentNodeOne;
    currentNodeOne = currentNodeOne.next;
  } else {
    mergedLinkedList = currentNodeTwo;
    currentNodeTwo = currentNodeTwo.next;
  }
  // Set initial pointer for mergedLinkedList
  const currentMergedLinkedListNode = mergedLinkedList;
  // While there are elements either linked lists, merge them together
  while (currentNodeOne || currentNodeTwo) {
    // If there are no nodes left on second list, push the rest of the first list
    if (!currentNodeSecond) {
      while (currentNodeOne) {
        currentMergedLinkedListNode.next = currentNodeOne;
        currentMergedLinkedListNode = currentMergedLinkedListNode.next;
        currentNodeOne = currentNodeOne.next;
      }
    }
    // If there are no nodes left on first list, push the rest of the second list
    if (!currentNodeOne) {
      while (currentNodeTwo) {
        currentMergedLinkedListNode.next = currentNodeTwo;
        currentMergedLinkedListNode = currentMergedLinkedListNode.next;
        currentNodeTwo = currentNodeTwo.next;
      }
    }
    if (currentNodeOne.value <= currentNodeTwo.value) {
      currentMergedLinkedListNode.next = currentNodeOne;
      currentMergedLinkedListNode = currentMergedLinkedListNode.next;
      currentNodeOne = currentNodeOne.next;
    }
    if (currentNodeOne.value > currentNodeTwo.value) {
      currentMergedLinkedListNode.next = currentNodeTwo;
      currentMergedLinkedListNode = currentMergedLinkedListNode.next;
      currentNodeTwo = currentNodeTwo.next;
    }
  }
}

/**
 * Converting sorted array to BST
 * O(N) runtime where N is the nubmer of elements in the array
 * Ideally this would be done iteratively,
 * but I have only heard of people doing this recursively
 */
function sortedArrayToBST(arr, start, end) {
  if (!arr) return;
  const mid = Math.floor(arr.length / 2);
  const left = sortedArrayToBST(arr, start, mid - 1);
  const right = sortedArrayToBST(arr, mid + 1, end);
  return new TreeNode({ val: arr[mid], left, right });
}

function mergeTrees(treeOne, treeTwo) {
  const sortedArrayOne = bstToSortedArray(treeOne);
  const sortedArrayTwo = bstToSortedArray(treeTwo);
  const mergedList = mergeTwoArrays(sortedArrayOne, sortedArrayTwo);
  return sortedArrayToBST(mergedList, 0, mergedList.length - 1);
}

/**
 * (3) Lowest common ancestry
 *
 * Find the paths to each node.
 * You can do this through a preorder traversal
 *
 * after finding the paths of the two target nodes, iterate through each array
 * When you find an index where the values are different, get the index prior to that
 * and return the value of that index
 *
 * ex: [1,2,3,6]
 * ex: [1,2,4]
 *
 * You can find the paths to each node by building an adjacency list,
 * or doing a preorder traversal
 */

function pathToNode(tree, targetNode) {
  if (!tree) return;
  if (tree.value === targetNode) return [targetNode];
  const leftPath = pathToNode(root.left, targetNode);
  // if either path returns a path, add current value to stack and return path
  if (leftPath) {
    leftPath.push(tree.value);
    return leftPath;
  }
  const rightPath = pathToNode(root.right, targetNode);
  if (rightPath) {
    rightPath.push(tree.value);
    return rightPath;
  }
  return null;
}

function findLowestCommonAncestor(root, firstNode, secondNode) {
  const pathToFirst = pathToNode(firstNode);
  const pathToSecond = pathToNode(secondNode);
  const lowestCommonAncestor = null;
  if (!pathToFirst || !pathToSecond) return;
  while (pathToFirst.length && pathToSecond.length) {
    const first = pathToFirst.pop();
    const second = pathToSecond.pop();
    if (first === second) {
      lowestCommonAncestor = first;
    } else {
      break;
    }
  }
  return lowestCommonAncestor;
}

Thanks for this! I was able to tidy up my mergeBST using arrays and I was stuck on the lowest common ancestor for a bit, haha. But, found some potential errors with the linkedList implementation:

I think there are some errors in bstToLinkedList? The while loop on line 121 never gets executed. On first pass, stack.length is 0, so falsey & currentNode is equal to tree, which is truthy, so !currentNode will be falsey. So, falsey || falsey will never loop through.

I changed it to stack.length || currentNode on my end for it to start looping through. As I see the code right now, though, it's going all the way down the left side of the tree and pushing that into stack --> then it sets the last node as currentNode --> so on the next iteration, it'll go into the if (currentNode) block again, so infinitely loop.

Still need more practice with LinkedList, so not sure how to revise it. Also, not sure what the solution to this problem with a LinkedList would be?

Also, TreeNode should have this.value = value (says right right now, hah)

Oh, and I have a cleaner implementation of mergeSortedArrays...let me know if you see something wrong with mine:

mergeTwoSortedArrays = (array1, array2) => {
    const arr = [];
    let i1 = 0, i2 = 0;
    while (i1 < array1.length || i2 < array2.length) {
        const e1 = array1[i1], e2 = array2[i2];
        if (e1 < e2) {
            arr.push(e1);
            i1++;
        } else {
            arr.push(e2);
            i2++;
        }
    }
    return arr;
}