Given a binary tree, design an algorithm which creates a linked list of all the nodes at each depth.

listOfDepths.ts

/*
  List of depths: Given a binary tree, design an algorithm which creates a linked list of all the nodes
  at each depth (eg if you have a tree with depth D, you'll have D linked lists.)

*/

interface DepthQueue<T> {
  depth: number,
  node: T
}

function listOfDepths<T>(head: BinaryNode<T>) {
  const listMap = new Map()
  const queue = new MyQueue<DepthQueue<BinaryNode<T>>>()
  listMap.set(0, new LinkedListNode(head))
  addChildrenToQueue(head, 1, queue)
  while (!queue.isEmpty()) {
    const { node, depth } = queue.remove().data 
    if (!listMap.get(depth)) {
      listMap.set(depth, new LinkedListNode(node))
    } else {
      listMap.get(depth).push(node)
    }
    addChildrenToQueue(node, depth + 1, queue)
  }
  return listMap
}

function addChildrenToQueue<T>(node: BinaryNode<T>, depth: number, queue: MyQueue<DepthQueue<BinaryNode<T>>>) {
  if (!node) return null
  if (node.leftChild) {
    queue.add({
      depth,
      node: node.leftChild
    })
  }
  if (node.rightChild) {
    queue.add({
      depth,
      node: node.rightChild
    })
  }
}


// given a sorted (increasing order) array with unique integer elements, write an algorithm to create a binary search tree with minial height.
class BinaryNode<T> {
  data: T
  leftChild: BinaryNode<T>
  rightChild: BinaryNode<T>

  constructor(data: T) {
    this.data = data
  }
}

class LinkedListNode<T> {
  next: LinkedListNode<T> 
  data: T

  constructor(node: BinaryNode<T>) {
    if (!node) return
    this.data = node.data
  }

  push = (newTail: LinkedListNode<T>) => {
    let node: LinkedListNode<T> = this
    while (node.next != null) {
      node = node.next
    }
    node.next = newTail
  }
}


// given a sorted (increasing order) array with unique integer elements, write an algorithm to create a binary search tree with minial height.
class BinaryNode<T> {
  data: T
  leftChild: BinaryNode<T>
  rightChild: BinaryNode<T>

  constructor(data: T) {
    this.data = data
  }
}

function buildTree(lst: number[]) {
  if (!lst || lst.length === 0) return null
  if (lst.length === 1) return new BinaryNode(lst[0])

  const medianIndex = Math.ceil((lst.length - 1) / 2)
  const node = new BinaryNode(lst[medianIndex])
  node.leftChild = buildTree(lst.slice(0, medianIndex))
  node.rightChild = buildTree(lst.slice(medianIndex + 1, lst.length))

  return node
}


const myTree = buildTree([1,2,3,4,5,6,7,8])

console.log(listOfDepths(myTree))