jingz8804

// this can be achieved by either depth first traversal or breadth first traversal
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class BTLists{
    // for depth first, we can use pre-order traversal
    public ArrayList<LinkedList<Node>> convertTreeToLists(Node root){
        ArrayList<LinkedList<Node>> result = new ArrayList<LinkedList<Node>>();
        convertTreeToLists(root, result, 0);
        return result;

jingz8804

public class BSTWithMinHeight{
    private class Node{
        int val;
        Node left;
        Node right;
        
        public Node(int val){
            this.val = val;
        }
    }

jingz8804

// we can use BFS to check if there is a path between two nodes.
// Assume that we have a Node class as follows:
// public class Node{
//     boolean isVisited = false;
//     ArrayList<Node> neighbors = new ArrayList<Node>();
// }
// if the Node class does not have a boolean attribute to indicate whether it has been visited or not,
// we can always create a wrapper class that wrap a Node and a boolean variable
import java.util.Queue;
import java.util.LinkedList;

jingz8804

// according to the question, a tree is balanced if and only if:
// 1. the left and right substrees are both balanced
// 2. the height difference between left and right are no greater than 1
// a natural recursion approach should be fine. but we do have to return two things together (isBalanced and height)
// so we can create a private wrapper class to do that. Or we can just return -1 as height if not balanced.

// Assume we have the following binary tree node
// public class BTNode{
//     BTNode left;
//     BTNode right;

jingz8804

import java.util.Date;
public class Animal{
    String type;
    Date arrived;
}

public class Dog extends Animal{
    String name;
    public Dog(String name){
        super();

jingz8804

// There are only a few known sorting algorithm and it is likely that we are facing a variation here.
// Let's look at these algorithms: merge sort, quick sort, insertion sort, bubble sort...
// Since we are only allowed to use one additional stack, we can rule out the first two.
// merge sort requires two additional data structures to merge to one (need 3?)
// quick sort does not seem to apply here since we need to hold the index and it seems hard to keep track of it.
// 
// What about insertion sort? Think about the pop/push and move/insert actions. They seem very similar! When we 
// are moving big numbers to insert a smaller number, it is similar to pop big numbers to another stack and then
// push the smaller number to this stack and then move the bigger numbers back. 
// 

jingz8804

import java.util.Stack;

public class MyQueue<E>{
    private Stack<E> s1;
    private Stack<E> s2;
    private int N = 0;
    
    public MyQueue(){
        s1 = new Stack<E>();
        s2 = new Stack<E>();

jingz8804

import java.util.Stack;

public class TowerOfHanoi {
	private class HanoiStack<E> extends Stack<E> {
		String name;

		public HanoiStack(String name) {
			super();
			this.name = name;
		}

jingz8804

import java.util.ArrayList;
import java.util.Stack;

public class SetOfStacks<E>{
    private int numOfStacks;
    private ArrayList<Stack<E>> stacks;
    private int capacity;
    
    public SetOfStacks(int capacity){
        this.capacity = capacity;

jingz8804

// With a normal stack, to find the min at any time, we have to scan through all elements in the stack
// and this is taking O(n) time. How can we know the min of the stack at any time or at any state immediately?
// One way to do it is to save the min of the stack in any state somewhere.
//
// push, pop and min operation of the following data structre takes amortized O(1) time.
public class StackWithMin{
    private int N;
    private int capacity;
    private int[] data;
    private int[] mins;