formation binary trees

binaryTree.js

// Binary Tree

//      10
//   5       15
// 1   7   12   20
//        11

// better graphical representation of a tree
// https://cdn.programiz.com/sites/tutorial2program/files/bst-vs-not-bst.png


// Plan:
// 2. Create the binary tree Node class (~3m)

class Node {
  constructor(val, left = null, right = null) {
    this.val = val
    this.left = left
    this.right = right
  }
}

// code representation of the Binary Tree at the top
let [leftLeft, leftRight, rightLeft, rightRight] = [
  new Node(1), new Node(7), new Node(12, new Node(11)), new Node(20)
];
let [left, right] = [new Node(5, leftLeft, leftRight), new Node(15, rightLeft, rightRight)];
let root = new Node(10, left, right);

function printTree(root) {
  let q = [root];
  const buf = [];
  while (q.length > 0) {
    const nextQ = [];
    for (const node of q) {
      buf.push(node.val.toString());
      buf.push(" ");
      if (node.left) nextQ.push(node.left);
      if (node.right) nextQ.push(node.right);
    }
    buf.push("\n");
    q = nextQ;
  }
  console.log(buf.join(""));
}

printTree(root);

// 4. Navigating binary tree problems (~30m)
//
// a. Calculate the depth of the tree (longest path)

//      10
//   5       15
// 1   7   12   20
//        11

function calculateMaxDepth(root) {
  if (!root) return 0;
  let leftDepth = calculateMaxDepth(root.left);
  let rightDepth = calculateMaxDepth(root.right);
  return Math.max(leftDepth, rightDepth) + 1
}

// console.log('depth', calculateMaxDepth(root));


// b. Calculate the sum of the entire tree

function sum(root) {
  if (!root) return 0

  return root.val + sum(root.left) + sum(root.right)
}

// console.log('sum', sum(root));

// Haskell
// Functional Programming Language (FP)
// Pure

// c. Search a binary search tree

function searchRegular(root, target) {
  if (!root) {
    return false
  }
  if (root.val === target) {
    return true
  }
  return (searchRegular(root.left, target) || searchRegular(root.right, target))
}

function searchBinary(root, target) {
  if (!root) {
    return false
  }
  if (root.val === target) {
    return true
  } else if (target < root.val) {
    return searchBinary(root.left, target);
  } else {
    return searchBinary(root.right, target);
  }
}

// for (const target of [10, 5, 15, 234, 345, 4567]) {
//   console.log('searchRegular', target, searchRegular(root, target));
// }

// for (const target of [10, 5, 15, 234, 345, 4567]) {
//   console.log('searchBinary', target, searchBinary(root, target));
// }

//      10
//   5       15
// 1   7   12   20
//        11

// 6. Validate if a binary tree is a binary search tree 
function validateTree(root) {
  function validate(node, max = Infinity, min = -Infinity) {
    if(!node) {
      return true;
    }

    if (node.val <= min || node.val >= max) {
      return false
    }

    return validate(node.left, node.val, min) && validate(node.right, max, node.val)
  }
  
  return validate(root);
}


[leftLeft, leftRight, rightLeft, rightRight] = [
  new Node(1), new Node(11), new Node(12, new Node(11)), new Node(20)
];
[left, right] = [new Node(5, leftLeft, leftRight), new Node(15, rightLeft, rightRight)];
root = new Node(10, left, right);
console.log(validateTree(root));