lienista

/*
we create 2 separate arrays of letters and count 
the number of characters resulting from the 
original precedence array.

we look up the index of each letter from first letter
array and follow the index of the next letter.
*/
function findWord(a){
  console.log(a);

lienista

// 4.9. BST Sequences: A BST was created by traversing through an array from left to right 
// and inserting each element. Given a binary search tree with distinct elements, print all 
// possible arrays that could have led to this tree.

import { BinaryTree } from "../helpers/tree.js";

const bstSequences = (root) => {
	
}

lienista

// 4.8. First Common Ancestor: Design an algorithm and write code to find 
// the first common ancestor of two nodes in a binary tree. Avoid storing 
// additional nodes in a data structure. Note: This is not necessarily a binary search tree.
import { BinaryTree } from "../helpers/tree.js";

const firstCommonAncestor = (root, p, q) =>{
  if(!root) 
    return null;
  
  //If p contains q, or q contains p

lienista

// 4.6. Follow up - Successor: Write an algorithm to find the "next" node (i.e., in-order successor) 
// of a given node in a BST. Node do not have a link to its parent. 
import { BinaryTree } from "../helpers/tree.js";

const inorderSuccessor = (root, p) => {
	if(!p) return null;

	//if node has right subtree, get the min of left subtree.
	if(p.right) return findMinLeft(p.right);
	if(!p.right) return closestAncestorAsLeftChild(root, p)

lienista

// 4.6. Successor: Write an algorithm to find the "next" node (i.e., in-order successor) 
// of a given node in a BST. You may assume that each node has a link to its parent.
import { BinaryTree } from "../helpers/tree.js";

const inOrderSuccessor = (root) => {
	if(!root) return null;

	//if node has right subtree, get the min of left subtree.
	if(root.right) return findMinLeft(root.right);
	if(!root.right) return closestAncestorAsLeftChild(root)

lienista

class BinaryTreeNode {
  constructor(value){
    this.value = value;
    this.parent = this.left = this.right = null;
  }
}

class BinaryTree {
  constructor(value){
    this.root = value || null;

lienista

// 4.5. Validate BST: Implement a function to check if a binary tree is a BST.
import { BinaryTree } from "../helpers/tree.js";

const isValidBST = (root) => {
	if(!root) return true;
	let check = {
    min: Number.NEGATIVE_INFINITY, 
    max: Number.POSITIVE_INFINITY,
  }
	return validateBST(root, check);

lienista

// 4.4 Check balanced: Implement a function to check if a binary tree is balanced. 
// For the purposes of this question, a balanced tree is defined to be a tree such 
// that the heights of the two subtrees of any node never differ by more than one.

class BinaryTreeNode {
  constructor(value){
    this.value = value;
    this.parent = this.left = this.right = null;
  }
}

lienista

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

class LinkedListNode(data) {
	constructor(data, next){
		this.data = data || null;
  	this.next = next || null;
	}
}

lienista

// 4.2. Minimal Tree:
// Minimal Tree: Given a sorted (increasing order) array with unique integer elements, 
// write an algorithm to create a binary search tree with minimal height.

class BinaryTreeNode {
  constructor(value){
    this.value = value;
    this.parent = this.left = this.right = null;
  }
}