Note of binary tree traverse and sorting algorithms

function displayPreOrderRecursive(root) {
	function preOrderHelper(node){
		if (node != null) {
			console.log(`node = ${node.val}`);
			preOrderHelper(node.left);
			preOrderHelper(node.right);
		}
	}
	if (root == null){
		console.log(`this is an empty tree`);
	} else {
		preOrderHelper(root);
	}
}

	 function displayPreOrderIterative() {
		//this will print out the root first, then left child, and right child
		// 1. Create an empty Stack
		// 2. Push the root into Stack
		// 3. Loop until Stack is empty
		// 4. Pop the last node and print its value
		// 5. Push right and left node if they are not null
		// 6. Repeat from step 4 to 6 again.

		let stack = [];
		stack.push(this.root);
		while (stack.length > 0) {
			let currentNode = stack.pop();
			console.log(`node = ${currentNode.val}`);
			if (currentNode.right != null) {
				stack.push(currentNode.right);
			}
			if (currentNode.left != null) {
				stack.push(currentNode.left);
			}
		}
	}

	function displayInOrderRecursive() {
		function inOrderHelper(node) {
			if (node != null) {
				inOrderHelper(node.left);
				console.log(`node = ${node.val}`);
				inOrderHelper(node.right);
			}
		}
		if (this.root == null) {
			console.log(`empty tree`);
			return;
		} else {
			inOrderHelper(this.root);
		}
	};

	function displayInOrderIterative() {
		let stack = [];
		let currentNode = this.root;
		stack.push(currentNode);
		currentNode = currentNode.left;

		while (stack.length > 0 || currentNode) {
			while(currentNode) {
				stack.push(currentNode);
				currentNode = currentNode.left;
			}

			currentNode = stack.pop();
			console.log(`node = ${currentNode.val}`);
			currentNode = currentNode.right;
		}
	}

	function displayPostOrderRecursive() {
		function postOrderHelper(node) {
			if (node != null) {
				postOrderHelper(node.left);
				postOrderHelper(node.right);
				console.log(`node = ${node.val}`);
			}
		}
		if (this.root == null){
			console.log(`this is an empty tree`);
		} else {
			postOrderHelper(this.root);
		}
	}

	function displayPostOrderIterative() {
		let stack1 = [];
		let stack2 = [];
		stack1.push(this.root);

		while(stack1.length > 0) {
			let currentNode = stack1.pop();
			console.log(`node = ${currentNode.val}`);
			stack2.push(currentNode);
			if (currentNode.left != null){
				stack1.push(currentNode.left);
			}
			if (currentNode.right != null){
				stack1.push(currentNode.right);
			}
		}

		while (stack2.length > 0) {
			console.log(`node = ${stack2.pop().val}`);
		}
	}

function binarySearch(nums, targetedNum) {
	nums.sort((a, b) => a-b); //ensure the nums is sorted array
	let leftIndex = 0;
	let rightIndex = nums.length - 1;

	let middleIndex = Math.floor((leftIndex + rightIndex)/2);

	while (rightIndex > leftIndex) {
		if (nums[middleIndex] == targetedNum) {
			return middleIndex;
		} else {
			if (nums[middleIndex] > targetedNum) {
				rightIndex = middleIndex - 1;
			} else {
				leftIndex = middleIndex + 1;
			}
			middleIndex = Math.floor((leftIndex + rightIndex)/2);

		}
	}
	return -1;
}

function binarySearch_recursive(nums, targetdNum) {
	nums.sort((a,b) => a-b);

	function bSearchHelper(nums, l, r, tNum) {
		if (r >= l) {
			let middleIndex = Math.floor((l + r)/2);
			if (nums[middleIndex] == tNum) return middleIndex;
			if (nums[middleIndex] > tNum) {
				r = middleIndex - 1;
			} else {
				l = middleIndex + 1;
			}
			return bSearchHelper(nums, l, r, tNum);			
		}

		return -1;
	}

	return bSearchHelper(nums, 0, nums.length-1, targetdNum);
}

function bubbleSort(unsortedArr) {
	console.log(`unsorted Arr = ${unsortedArr}`);
	let swap = false;
	let iteration = 0;

	for (let i = 0; i < unsortedArr.length - 1; i ++) {
		for (let j = 0; j < unsortedArr.length; j ++) {
			if (unsortedArr[j] > unsortedArr[j+1]) {
				swap = true;
				let temp = unsortedArr[j];
				unsortedArr[j] = unsortedArr[j+1];
				unsortedArr[j+1] = temp;
			}			
		}
		iteration += 1;
	}
	console.log(`iteration = ${iteration}, sortedArr = ${unsortedArr}`);
}

function insertionSort(arr) {
	if (arr == null || arr.length <= 1) return arr;

	console.log(`unsorted array = ${arr}`);


	for (let i = 1; i < arr.length; i++){
		let currentIndex = i;
		let currentValue = arr[currentIndex];
		let j = i - 1;
		while(j >= 0 &&  arr[j] > currentValue){
			arr[j+1] = arr[j];
			j -= 1;
		}
		arr[j+1] = currentValue;
	}
	console.log(`sorted array = ${arr}`);
}

function selectionSort(arr) {
	console.log(`Unsorted Array = ${arr}`);
	let startingIndex = 0;
	while (startingIndex < arr.length){
		let minIndex = startingIndex;
		for (let i = startingIndex + 1; i < arr.length; i++){
			if (arr[minIndex] > arr[i]) {
				minIndex = i;
			}
		}
		if (minIndex != startingIndex) {
			console.log(`minValueIndex = ${minIndex}, 
				startingIndex = ${startingIndex} `);
			let temp = arr[startingIndex];
			arr[startingIndex] = arr[minIndex];
			arr[minIndex] = temp;
		}
		startingIndex += 1;
	}
	console.log(`Selection Sorting => ${arr}`);
}

function mergeSort(unsortedArr) {
	if (unsortedArr == null || unsortedArr.length <= 1) return unsortedArr;

	let m = Math.floor(unsortedArr.length/2);

	let left = (unsortedArr.slice(0, m));
	let right = (unsortedArr.slice(m));

	let sortedArr =  merge(mergeSort(left), mergeSort(right));
	console.log(sortedArr);
	return sortedArr;

}

function merge(left, right) {
	let sortedArr = [];
	let leftIndex = 0;
	let rightIndex = 0;

	while(leftIndex < left.length && rightIndex < right.length) {
		if (left[leftIndex] < right[rightIndex]) {
			sortedArr.push(left[leftIndex]);
			leftIndex += 1;
		} else {
			sortedArr.push(right[rightIndex]);
			rightIndex += 1;
		}
	}
	return sortedArr.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

function quickSort_recursive(arr){
	if (arr == null || arr.length <= 1) return arr;

	let left = [];
	let right = [];
	let newArr = [];
	let pivot = arr.pop();

	for (let i = 0; i < arr.length; i++){
		if (arr[i] > pivot) {
			right.push(arr[i]);
		} else {
			left.push(arr[i]);
		}
	}

	return newArr.concat(quickSort_recursive(left), pivot, quickSort_recursive(right));
}