jack-wong-build’s gists

jack-wong-build / createMinimalBST

Created January 12, 2014 20:13

Given a sorted (increasing order) array, write an algorithm to create a binary tree with minimal height

	var createMinimalBST = function(array){
	var makeNode = function(value){
	var obj = {
	value:value,
	left:null,
	right:null
	};
	return obj;
	};

jack-wong-build / findLevelLinkedList

Created January 13, 2014 03:09

Given a binary search 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)

	var findLevelLinkedList = function(root){

	var queue = [];
	var linkedListArray = [];
	var level = 0;

	queue.push([root, level]);
	root.visit = true;

	while(queue.length !== 0){

jack-wong-build / inOrderSucc

Created January 13, 2014 05:23

Write an algorithm to find the ‘next’ node (e g , in-order successor) of a given node in a binary search tree where each node has a link to its parent

	var inOrderSucc = function(node){
	var p = null;

	if (node !== null){
	if (node.parent === null \|\| node.right !== null){
	p = leftMostChild(node.right);
	console.log("result=", p);
	} else {
	while ((p = node.parent) !== null){
	if (p.left === node){

jack-wong-build / mergeSort

Last active August 29, 2015 13:56

Merge sort

	function mergeSort(array, start, end){

	if (start === end) return [array[start]];

	var mid = Math.floor( (start + end) / 2 );

	var arr1 = mergeSort(array, start, mid);
	var arr2 = mergeSort(array, mid+1, end);
	var result = merge(arr1, arr2);

jack-wong-build / findSortedArrayOcurrence

Created February 13, 2014 11:04

Given a sorted array arr[] and a number x, write a function that counts the occurrences of x in arr[]. Expected time complexity is O(Logn).

	//1,2,3,4,4,4,4,4,5,6,7

	function findFrequency(array, target){
	var first, last;
	var result = -1;

	first = findFirst(array, target, 0, array.length-1);

	if (first !== -1){
	last = findLast(array, target, 0, array.length-1);

jack-wong-build / checkBST

Created February 17, 2014 18:21

Implement a function to check if a binary tree is a binary search tree.

	function checkBST(node){

	lastVisited = null;

	function checkBSTRecurse (node){
	if (node === null) return true;

	if ( !checkBSTRecurse(node.left) ) return false;

	if (node.val < lastVisited) return false;

jack-wong-build / containTrees

Created February 17, 2014 19:05

Create an algorithm to decide if T2 is a subtree of T1.


	function containTrees(tree1, tree2){
	if (tree2 === null){
	return true;
	}

	return subTree(tree1, tree2);
	}

	function subTree(tree1, tree2){

jack-wong-build / createMinimalBST

Created February 17, 2014 20:04

Given a sorted array, write an algorithm to create a binary search tree with minimal height.

	function createMinimalBST(array, start, end){
	if (end < start){
	return null;
	}

	var mid = Math.floor( (start + end) / 2 );

	var node = {val: array[mid], left: null, right: null};
	node.left = createMinimalBST(array, start, mid-1);
	node.right = createMinimalBST(array, mid+1, end);

jack-wong-build / commonAncestor

Created February 18, 2014 05:16

Find the first common ancestor of two nodes in a binary tree. Avoid storing additional nodes in a data structure.

	function covers(root, node){
	if (root === null ) return false;
	if (root === node ) return true;
	return covers(root.left, node) \|\| covers(root.right, node);
	}

	function commonAncestorHelper(root, node1, node2){
	if (root === null ) return false;
	if (root === node1 \|\| root === node2 ) return root;

jack-wong-build / quickSort

Last active August 29, 2015 13:56

Quick sort.

	function quickSort(array, start, end){

	var leftIndex = partition(array, start, end);

	if (start < leftIndex-1){
	quickSort(array, start, leftIndex-1);
	}

	if (start > leftIndex){
	quickSort(array, leftIndex, end);

Jack Wong jack-wong-build