binary_tree.ts

const LEAFES = ['left', 'right'] as const;

const hasProperty = <Obj, Prop extends string>(obj: Obj, prop: Prop)
  : obj is Obj & Record<Prop, unknown> =>
  Object.prototype.hasOwnProperty.call(obj, prop);


const withChildren = <
  Type extends Box
>(btree: TreeNode<Type>)
  : btree is WithChildren<Type> =>
  LEAFES.every(elem => hasProperty(btree, elem))

type Comparable<T = number> = {
  value: T;
  gt: (x: T) => boolean;
  ls: (x: T) => boolean;
  eq: (x: T) => boolean;
}

type Value<T = number> = { value: T }

type Box = Comparable & Value


type WithoutChildren<Type extends Box> =
  { data: Type }

type WithChildren<Type extends Box> =
  { data: Type, left: TreeNode<Type>, right: TreeNode<Type> }




type TreeNode<Type extends Box> =
  | null
  | { data: Type, left: TreeNode<Type>, right: TreeNode<Type> }



const node = (
  data: Box,
  left: TreeNode<Box> = null,
  right: TreeNode<Box> = null
): TreeNode<Box> => ({ data, left, right })

const value = (value: number): Value<number> => ({ value })

const comparable = ({ value }: Value<number>
): Box =>
({
  value,
  gt: (x: number) => value > x,
  ls: (x: number) => value < x,
  eq: (x: number) => x === value
})

// const cmpValue = compose(comparable, value);

// const leaf = compose(node, cmpValue)

const root = node(
  comparable(value(10)),
  node(comparable(value(5))),
  node(comparable(value(30)))
)


const insert = (bTree: TreeNode<Box>, value: Box)
  : TreeNode<Box> => {
  if (bTree === null) {
    return node(value)
  }

  const { left, right, data } = bTree;

  if (value.ls(data.value)) {
    return node(data, insert(left, value), right)
  }

  if (value.gt(data.value)) {
    return node(data, left, insert(right, value))
  }

  return bTree
}

const treeLength = (bTree: TreeNode<Box>, length = 0): number => {
  if (bTree === null) {
    return length
  }

  const { left, right } = bTree;

  return treeLength(left, length) + treeLength(right, length) + 1

}

const result = insert(root, comparable(value(4)))



const treeHeight = (bTree: TreeNode<Box>,): number => {
  if (bTree === null) {
    return 0
  }

  const { left, right } = bTree;

  return 1 + Math.max(treeHeight(left), treeHeight(right))
}


console.log('RESULT::', treeHeight(result))

{
class TreeNode {
    val: number
    left: TreeNode | null
    right: TreeNode | null
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val === undefined ? 0 : val)
        this.left = (left === undefined ? null : left)
        this.right = (right === undefined ? null : right)
    }
}

const toTree = (arr: Array<number | null>, start = 0, end = arr.length - 1) => {
    if (start > end) {
        return null
    }
    var mid = Math.floor((start + end) / 2)
    const root = new TreeNode(arr[mid]);
    root.left = toTree(arr, start, mid - 1)
    root.right = toTree(arr, mid + 1, end)

    return root

}


function deepestLeavesSum(
    root: TreeNode | null,
    maxSize: number,
    level = 0,

): number {
    if (!root) {
        return 0
    }
    console.log({maxSize,level})
    if (!root.left && !root.right && maxSize-1 === level) {
        return root.val
    }

    level++

    const left = deepestLeavesSum(root.left, maxSize, level)
    const right = deepestLeavesSum(root.right, maxSize, level)
    return left + right
};

const tree = new TreeNode(1,
    new TreeNode(2,
        new TreeNode(4, new TreeNode(7)),
        new TreeNode(5)),
    new TreeNode(3, null,
        new TreeNode(6, null, new TreeNode(8))
    ))


console.log(deepestLeavesSum(tree, treeHeight(tree)))
}

const binarySearch = (list: number[], elem: number, start = 0, end = list.length - 1) => {
  if (start >= end) {
    return -1
  }

  const mid = Math.floor((start + end) / 2);
  if (list[mid] === elem) {
    return mid
  }
  if (elem > list[mid]) {
    return binarySearch(list, elem, mid + 1, end)
  }
  if (elem < list[mid]) {
    return binarySearch(list, elem, start, mid - 1)

  }


}