Some data structures and algorithms in Java

README.md

Data structures and algorithms in Java

BinarySearchTree.java

public class BinarySearchTree {

    public static Node root;

    public BinarySearchTree() {
        this.root = null;
    }

    public boolean find(int id) {
        Node current = root;
        while (current != null) {
            if (id == current.data) {
                return true;
            } else if (id > current.data) {
                current = current.right;
            } else {
                current = current.left;
            }
        }
        return false;
    }

    public void insert(int id) {
        Node newNode = new Node(id);
        if (root == null) {
            root = newNode;
            return;
        }

        Node current = root;

        while (true) {
            if (id < current.data) {
                if (current.left == null) {
                    current.left = newNode;
                    return;
                } else {
                    current = current.left;
                }
            } else if (id > current.data) {
                if (current.right == null) {
                    current.right = newNode;
                    return;
                } else {
                    current = current.right;
                }
            } else {
                return;
            }
        }
    }

    public boolean delete(int id) {

        Node parent = null;
        Node current = root;
        boolean isLeftChild = false;

        while (current.data != id) {
            parent = current;
            if (id > current.data) {
                current = current.right;
                isLeftChild = false;
                if (current == null) {
                    System.out.println("Node " + id + " not found");
                    return false;
                }
            } else {
                current = current.left;
                isLeftChild = true;
                if (current == null) {
                    System.out.println("Node " + id + " not found");
                    return false;
                }
            }
        }

        if (current.left == null && current.right == null) {
            if (current == root) {
                root = null;
            }
            if (isLeftChild) {
                parent.left = null;
            } else {
                parent.right = null;
            }
        }

        else if (current.left == null) {
            if (current == root) {
                root = current.right;
            } else {
                if (isLeftChild) {
                    parent.left = current.right;
                } else {
                    parent.right = current.right;
                }
            }
        }

        else if (current.right == null) {
            if (current == root) {
                root = current.left;
            } else {
                if (isLeftChild) {
                    parent.left = current.left;
                } else {
                    parent.right = current.left;
                }
            }
        }

        else {
            // left and right child nodes are not null
            Node successor = getSuccessor(current);
            if (current == root) {
                root = successor;
            } else if (isLeftChild) {
                parent.left = successor;
            } else {
                parent.right = successor;
            }
            successor.left = current.left;
        }
        return true;
    }

    public Node getSuccessor(Node deleteNode) {
        Node successor = null;
        Node successorParent = null;
        Node current = deleteNode.right;

        while (current != null) {
            successorParent = successor;
            successor = current;
            current = current.left;
        }

        if (successor != deleteNode.right) {
            successorParent.left = successor.right;
            successor.right = deleteNode.right;
        }
        return successor;
    }

    public static void display(Node root) {
        if (root != null) {
            display(root.left);
            System.out.println(" " + root.data);
            display(root.right);
        }
    }

    public static void main(String[] args){
        BinarySearchTree b = new BinarySearchTree();
        b.insert(3);b.insert(8);
        b.insert(1);b.insert(4);b.insert(6);b.insert(2);b.insert(10);b.insert(9);
        b.insert(20);b.insert(25);b.insert(15);b.insert(16);
        System.out.println("Original Tree : ");
        b.display(b.root);
        System.out.println("");
        System.out.println("Check whether Node with value 4 exists : " + b.find(4));
        System.out.println("Check whether Node with value 5 exists : " + b.find(5));
        System.out.println("Delete Node with no children (2) : " + b.delete(2));
        b.display(b.root);
        System.out.println("\n Delete Node with one child (4) : " + b.delete(4));
        b.display(b.root);
        System.out.println("\n Delete Node with Two children (10) : " + b.delete(10));
        b.display(b.root);
    }
}

MergeSort.java

import java.util.ArrayList;

public class MergeSort {

  ArrayList<Integer> merge(ArrayList<Integer> A, ArrayList<Integer> B) {

    ArrayList<Integer> merged = new ArrayList<Integer>();

    int i = 0,
        j = 0;

    while (i < A.size() && j < B.size()) {

      if (A.get(i) < B.get(j)) {
        merged.add(A.get(i));
        i++;
      } else {
        merged.add(B.get(j));
        j++;
      }
    }

    for (int w = i; w < A.size(); w++) {
      merged.add(A.get(w));
    }
    for (int z = j; z < B.size(); z++) {
      merged.add(B.get(z));
    }

    return merged;
  }

  ArrayList<Integer> mergeSort(ArrayList<Integer> arr) {

    int arrLength = arr.size();

    if (arrLength <= 1) { return arr; }

    int x = arrLength / 2;
    int index = (arrLength % 2 == 0) ? x : x + 1;
    
    ArrayList<Integer> firstHalf = new ArrayList<Integer>();
    ArrayList<Integer> secondHalf = new ArrayList<Integer>();

    for (int i = 0; i < arrLength; i++) {
      if (i < index) { 
        firstHalf.add(arr.get(i));
      } else {
        secondHalf.add(arr.get(i));
      }
    }

    return merge(mergeSort(firstHalf), mergeSort(secondHalf));
  }
}

Node.java

class Node {
    int data;
    Node left;
    Node right;
    public Node(int data) {
        this.data = data;
        left = null;
        right = null;
    }

    public String toString() {
        return "Node(data=" + data + ", left=" + left + ", right=" + right + ")";
    }
}

NumberStuff.java

public class NumberStuff {

    // implementing built-in java functions

    public int factorial(int n) {
        if (n < 0) {
            System.out.println("input to factorial function must be an integer >= 0");
            throw new IllegalArgumentException();
        } else if (n < 2) {
            return 1;
        } else {
            int temp = 1;
            for (int i = n; i > 0; i--) {
                temp *= i;
            }
            return temp;
        }
    }

    public static double pow(double a, int b) {

        double temp = 1.0;
        for (int i = 0; i < b; i++) {
            temp *= a;
        }
        return temp;
    }

    public static double exp(int n) {
        double e = 2.718281828;
        return pow(e, n);
    }

    public static int fibonacci(int n) {
        if (n < 0) {
            System.out.println("Fibonacci function is only defined for positive integers");
            throw new IllegalArgumentException();
        } else if (n < 2) {
            return n;
        } else {
            int a = 0;
            int b = 1;
            int temp = 0;
            for (int i = 2; i < n; i++) {
                temp = a + b;
                a = b;
                b = temp;
            }
            return a + b;
        }
    }
}

Permutator.java

/*
Problem: create a function that generates all permutations of an
input string. For simplicity, assumes all characters in the input
string are unique.
e.g. p('a') => ['a']
     p('abc') => ['abc', 'cab', 'acb', 'bac', 'cba', 'bca']
 */

import java.util.*;

public class Permutator {

    public static List<String> permute(String str) {

        List<String> permutations = new ArrayList<>();
        int n = str.length();

        if (n < 2) {
            permutations.add(str);
            return permutations;
        }

        char lastLetter = str.charAt(n - 1);
        List<String> base = permute(str.substring(0, n - 1));

        for (String perm: base) {
            String newPerm = perm + lastLetter;
            permutations.add(newPerm);
            for (int i = 0; i < perm.length(); i++) {
                String firstHalf = perm.substring(0, i);
                String secondHalf = perm.substring(i, perm.length());
                newPerm = firstHalf + lastLetter + secondHalf;
                permutations.add(newPerm);
            }
        }
        return permutations;
    }
}

QuickSort.java

import java.util.Arrays;
import java.util.ArrayList;

public class QuickSort {

  ArrayList<Integer> concat(ArrayList<Integer> A, ArrayList<Integer> B) {
    ArrayList<Integer> C = new ArrayList<Integer>();
    for (int i = 0; i < A.size(); i++) {
      int val = A.get(i);
      C.add(val);
    }
    for (int i = 0; i < B.size(); i++) {
      int val = B.get(i);
      C.add(val);
    }
    return C;
  }

  ArrayList<Integer> quickSort(ArrayList<Integer> arr) {

    if (arr.size() < 2) {
      return arr;
    } else { 

      int pivot = arr.get(arr.size() - 1);
      int currVal = 0;

      ArrayList<Integer> lessThan = new ArrayList<Integer>();
      ArrayList<Integer> equalTo = new ArrayList<Integer>();
      ArrayList<Integer> greaterThan = new ArrayList<Integer>();

      for (int i = 0; i < arr.size(); i++) {
        currVal = arr.get(i);
        if (currVal < pivot) { lessThan.add(currVal); }
        else if (currVal > pivot) { greaterThan.add(currVal); }
        else { equalTo.add(currVal); }
      }

      ArrayList<Integer> temp = concat(quickSort(lessThan), equalTo);
      ArrayList<Integer> result = concat(temp, quickSort(greaterThan));

      return result;
    }
  }
}

TestMergeSort.java

import java.util.Arrays;
import java.util.ArrayList;

public class TestMergeSort {

  public static ArrayList<Integer> randArrayList(int n) {

    ArrayList<Integer> randArr = new ArrayList<Integer>();
    
    for (int i = 0; i < n; i++) {
      randArr.add(((int)Math.floor(Math.random() * n)));
    }

    return randArr;
  }

  public static void timeIt(int arrLength, int nLoops) {

    long start = System.currentTimeMillis();

    for (int i = 0; i < nLoops; i++) {
    
      ArrayList<Integer> arr = randArrayList(arrLength);

      MergeSort Sorter = new MergeSort();
      
      ArrayList<Integer> result = Sorter.mergeSort(arr);

      if (!verifySort(result)) {
        System.out.println("mergeSort failed at iteration " + i);
        System.out.println("  input:  " + arr);
        System.out.println("  result:  " + result);
        break;
      }
    }

    long end = System.currentTimeMillis();

    System.out.println("sorted " + nLoops + " random arrays of length " + arrLength);
    System.out.println("  in " + ((end - start) / 1000.) + " seconds");
    
  }

  public static boolean verifySort(ArrayList<Integer> arr) {

    for (int i = 0; i < arr.size() - 1; i++) {
      if (arr.get(i) > arr.get(i + 1)) {
        return false;
      }
    }
    return true;
  }

  public static void main(String[] args) {
    ArrayList<Integer> arr = randArrayList(15);
    MergeSort Sorter = new MergeSort();
    ArrayList<Integer> sortedArr = Sorter.mergeSort(arr);
    System.out.println("input array:         " + arr);
    System.out.println("sorted input array:  " + sortedArr);

    timeIt(50, (int)Math.pow(10, 4));
  }
}

TestNumberStuff.java

public class TestNumberStuff {

    public static void main(String[] args) {
        NumberStuff fun = new NumberStuff();
        System.out.println(fun.factorial(5));
        System.out.println(fun.pow(10, 4));
        double e = 2.718281828;
        System.out.println("e^3:  " + e*e*e);
        System.out.println("e^3:  " + fun.exp(3));
        System.out.println(fun.fibonacci(8));
    }
}

TestPermutator.java

import java.util.*;

public class TestPermutator {

    public static void main(String[] args) {

        List<String> strList = Arrays.asList("a", "ab", "abc", "abcd");
        Permutator p = new Permutator();

        for (String str: strList) {
            System.out.println("\npermutating string:  " + "'" + str + "'");
            System.out.println("permutations:  " + p.permute(str));
        }
    }
}

TestQuickSort.java

import java.util.Arrays;
import java.util.ArrayList;

public class TestQuickSort {

  public static ArrayList<Integer> randArrayList(int n) {

    ArrayList<Integer> randArr = new ArrayList<Integer>();
    
    for (int i = 0; i < n; i++) {
      randArr.add(((int)Math.floor(Math.random() * n)));
    }

    return randArr;
  }

  public static void timeIt(int arrLength, int nLoops) {

    long start = System.currentTimeMillis();

    for (int i = 0; i < nLoops; i++) {
    
      ArrayList<Integer> arr = randArrayList(arrLength);

      QuickSort Sorter = new QuickSort();
      
      ArrayList<Integer> result = Sorter.quickSort(arr);

      if (!verifySort(result)) {
        System.out.println("quicksort failed at iteration " + i);
        System.out.println("  input:  " + arr);
        System.out.println("  result:  " + result);
        break;
      }
    }

    long end = System.currentTimeMillis();

    System.out.println("sorted " + nLoops + " random arrays of length " + arrLength);
    System.out.println("  in " + ((end - start) / 1000.) + " seconds");
    
  }

  public static boolean verifySort(ArrayList<Integer> arr) {

    for (int i = 0; i < arr.size() - 1; i++) {
      if (arr.get(i) > arr.get(i + 1)) {
        return false;
      }
    }
    return true;
  }

  public static void main(String[] args) {
    ArrayList<Integer> arr = randArrayList(15);
    QuickSort Sorter = new QuickSort();
    ArrayList<Integer> sortedArr = Sorter.quickSort(arr);
    System.out.println("input array:         " + arr);
    System.out.println("sorted input array:  " + sortedArr);

    timeIt(1000, (int)Math.pow(10, 3));
  }
}

TestUnionizer.java

import java.util.*;

public class TestUnionizer {

    private static Tuple first = new Tuple(1, 3);
    private static Tuple second = new Tuple(1, 6);
    private static Tuple third = new Tuple(8, 10);
    private static Tuple fourth = new Tuple(9, 12);

    public static Tuple randRange(int n) {
        int lower = (int)Math.floor(Math.random() * n);
        int margin = (int)Math.floor(Math.random() * 10) + 1;
        int upper;
        if (lower + margin > n) {
            upper = n;
        } else {
            upper = lower + margin;
        }
        return new Tuple(lower, upper);
    }

    public static void testRandRange() {
        List<Tuple> randRanges = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            Tuple randomRange = randRange(50);
            System.out.println("random range generated:  " + randomRange);
            randRanges.add(randomRange);
        }
        System.out.println("\n");
    }

    public static void testMerge() {

        Unionizer unionizer = new Unionizer();

        Tuple result = unionizer.merge(first, second);
        System.out.println("merge " + first + ", " + second + "  =>  " + result);

        result = unionizer.merge(first, third);
        System.out.println("merge " + first + ", " + third + "  =>  " + result);

        result = unionizer.merge(first, fourth);
        System.out.println("merge " + first + ", " + fourth + "  =>  " + result);

        result = unionizer.merge(second, third);
        System.out.println("merge " + second + ", " + third + "  =>  " + result);

        result = unionizer.merge(second, fourth);
        System.out.println("merge " + second + ", " + fourth + "  =>  " + result);

        result = unionizer.merge(third, fourth);
        System.out.println("merge " + third + ", " + fourth + "  =>  " + result);

        System.out.println("\n");
    }

    public static void testUnionize() {

        Unionizer unionizer = new Unionizer();

        List<Tuple> testRanges = new ArrayList<>();
        testRanges.add(first);
        testRanges.add(second);
        testRanges.add(third);
        testRanges.add(fourth);

        System.out.println("test ranges:       " + testRanges);
        List<Tuple> result = unionizer.unionize(testRanges);
        System.out.println("unionized result:  " + result + "\n");

        List<Tuple> ranges = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            Tuple randomRange = randRange(30);
            ranges.add(randomRange);
            System.out.println("random range generated:  " + randomRange);
        }
        System.out.println("rand ranges:  " + ranges);
        result = unionizer.unionize(ranges);
        System.out.println("unionized result:  " + result);

        System.out.println("\n");
    }

    public static void main(String[] args) {
        System.out.println("\n\nTesting Unionizer methods:\n\n");
        testRandRange();
        testMerge();
        testUnionize();
    }
}

Tuple.java

public class Tuple {

    public final int first;
    public final int second;

    public Tuple(int x, int y) {
        if (x > y) {
            throw new IllegalArgumentException("range must be non decreasing");
        } else {
            this.first = x;
            this.second = y;
        }
    }

    public String toString() {
        return "(" + this.first + ", " + this.second + ")";
    }
}

Unionizer.java

/*
Problem: create a function that takes in a list of integer ranges
and returns the union of all ranges.
e.g. f([(1, 3), (1, 6), (8, 10)]) => [(1, 6), (8, 10)]
 and f([(1, 3), (8, 10)]) => [(1, 3), (8, 10)].
*/

import java.util.*;

public class Unionizer {

    public Tuple merge(Tuple a, Tuple b) {

        boolean ordered = false;

        if (a.first < b.first) {
            ordered = true;
        } else {
            if (a.first == b.first) {
                if (a.second < b.second) {
                    ordered = true;
                } else {
                    if (a.second == b.second) {
                        return null;
                    }
                }
            }
        }

        if (!ordered) {
            Tuple temp = a;
            a = b;
            b = temp;
        }

        if (a.second < b.first) {
            // then no overlap; return null
            return null;
        } else {
            int upper = Math.max(a.second, b.second);
            return new Tuple(a.first, upper);
        }
    }

    public List<Tuple> unionize(List<Tuple> ranges) {
        if (ranges.size() < 2) {
            return ranges;
        }

        boolean merged = false;

        for (int i = 0; i < ranges.size() - 1; i++) {
            Tuple range1 = ranges.get(i);
            for (int j = i + 1; j < ranges.size(); j++) {
                Tuple range2 = ranges.get(j);
                Tuple result = merge(range1, range2);
                if (result != null) {
                    ranges.remove(range1);
                    ranges.remove(range2);
                    ranges.add(result);
                    merged = true;
                    break;
                }
            }
            if (merged) {
                break;
            }
        }
        if (!merged) {
            return ranges;
        } else {
            return unionize(ranges);
        }
    }
}