recursion.java

public int factorial(int n) {
    if (n == 0)
        return 1;
    else
        return n * factorial(n-1);
}

public int rangeSum(int[] array, int start, int end) {
    if (start > end)
        return 0;
    else
        return array[start] + rangeSum(array, start+1, end);
}

public int fib(int n) {
    if (n == 0)
        return 0;
    else if (n == 1)
        return 1;
    else
        return fib(n-1) + fib(n-2);
    
}
/*
-> Fnd the midpoint of the array
-> Check the value at the midpoint
    -> If target < value, then perform binray search on the first half of the array
    -> If trget > value, then perform binary search on the secomd half of the array
    -> If target == value, then return the index because we found the target


*/

public int binarySearch(int[] nums, int target) {
    int len = nums.length();
    
    int lo, hi = 0, len;
    
    while (lo <= hi) {
        double val = (lo + hi) / 2;
        int mid = Math.floor(val);
        if (nums[mid] == targe)
            return mid;
        else if (nums[mid] < target)
            lo = mid + 1;
        else
            hi = mid - 1;
    }
    return -1;
}

public int modifiedBinarySearch(int[] nums, int target) {
    int len = nums.length();
    
    int lo, hi = 0, len;
    
    while (lo <= hi) {
        double val = (lo + hi) / 2;
        int mid = Math.floor(val);
        if (nums[mid] == targe)
            return mid;
        else if (nums[mid] < target)
            lo = mid + 1;
        else
            hi = mid - 1;
    }
    return -1;
}

/*

runtime - O(logN)
space - O(1)

while (lo != mid && arr[mid]==arr[lo])
case 1: arr[lo] > arr[mid] ; then its rotated
if target >= arr[lo] or target <= arr[mid]
hi = mid - 1;
else: lo = mid + 1
else: 
case 2: 
if targ > arr[mid]
lo = mid + 1;
else hi = mid - 1

*/

public int searchRotateArrayWithDuplicates(int[] arr, int target) {
    int lo = 0;
    int hi = arr.length - 1;
    
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        
        if (arr[mid] == target)
            return mid
        
        while (lo != mid && arr[mid] == arr[lo]) {
            lo++;
        }
        
        if (arr[lo] > arr[mid])
            if (target >= arr[lo] || target <= arr[mid])
                hi = mid - 1;
            else
                lo = mid + 1;
        else
            if (nums[mid] < target)
                lo = mid + 1;
            else
                hi = mid + 1;
    }
}

/*
first find the left range & then using left as a 
lo find the right range. Then return the array
*/




public int findMin(int[] arr, int target) {
    int lo = 0;
    int hi = arr.length - 1;
    int left = binarySearch(nums, lo, hi, target)
    if (left == -1) {
        return null;
    }
    int right = binarySearch(nums, left, hi, target)
    return [left, right];
    
}

public binarySearch(int[] nums, int lo, int hi, int target) {
    while (lo <= hi) {
        int mid = (lo + hi)/2;
        if (nums[mid] == target) {
            return mid;
        }
        else if (nums[mid] < target) {
            lo = mid + 1;
        }
        else {
            hi = mid - 1;
        }
    }
    return -1;
}




public int binarySearchFindMin(int[] arr) {
    int lo = 0;
    int hi = arr.length - 1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (nums[mid] > nums[hi]) {
            lo = mid + 1;
        }
        else {
            hi = mid;
        }
    }
    return nums[lo];
}


public boolean matrixBS(int[][] matrix, int target) {
    int rows = matrix.length;
    int cols = matrix[0].length;
    int low = 0;
    int hi = rows * cols - 1;
    
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        int nums = matrix[mid/cols][mid % cols];
        if (matrix[nums) == target)
            return true;
        else if (matrix[nums] > target) {
            hi = mid - 1;
        }
        else {
            lo = mid + 1;
        }
    }
    return false;
    
}


/*
level order traversal: initialize Q and add root to the Q
then using a loop deQ & print root. then enQ left & right

*/


public int levelOrderTraversal(TreeNode root) {
    Queue<Integer> pQueue = new PriorityQueue<Integer>();
    pQueue.add(root);
    while(pQueue.length) {
        int cur = pQueue.poll();
        if(cur != null) {
            System.out.println(cur);
            pQueue.add(cur.left);
            pQueue.add(cur.right);
        }
    }
    
}

/* Sum of left leaves
if (root== null) return 0;
sum = 0
if root.left != null
if (root.left.left == null && root.left.right == null)
ans != root.left.val
else ans += sumOfLeftLeaves(root.left)
ans += sumOfLeftLeaves(root.right)
*/



public int sumOfLeftLeaves(root) {
    if (root == null) return 0;
    int sum = 0;
    if (root.left != null) {
        if (root.left.left == null && root.left.right == null) {
            sum += root.left.val;
        }
        else {
            sum += sumOfLeftLeaves(root.left);
        }
    }
    sum += sumOfLeftLeaves(root.right);
    
}


/*
initialize a stack check (if root == null) return 0;
sum = 0; stack.push root then using a loop pop the first
element then check the condition if ans += node.left.val
else push left or right

*/


public int sumOfLeftLeaves(TreeNode root) {
    if (root == null)
        return 0;
    int sum = 0;
    Stack<TreeNode> stack = new Stack<TreeNode>();
    stack.push(root);
    while(!stack.empty()) {
        TreeNode root = stack.pop();
        if (root.left != null)
            if (root.left.left == null && root.left.right == null)
                sum += root.left.val;
            else
                stack.push(root.left);
        if (root.right != null)
            if (root.right.left == null && root.right.right == null)
                sum += root.right.val;
            else
                sum += root.right.val;

    }
    return sum;
}


/*
first set cur to root & parent to null then using a loop
while root != null set parent = cur if cur.val < val : 
cur = cur.right else cur = cur.left

if (parent.val < val) parent.right = new TreeNode(val)
else parent.left = new TreeNode(val)
return root;

*/


public TreeNode insertIntoBST(TreeNode root, int val) {
    TreeNode cur = root;
    TreeNode parent = null;
    
    while (cur != null) {
        parent = cur;
        if (curr.val < val)
            cur = cur.right;
        else
            cur = cur.left;
    }
    if (parent.val < val) {
        parent.right = new TreeNode(val);
    }
    else
        parent.left = new TreeNode(val);
}



/*
maxDepth 
*/

public int maxDepth(TreeNode root) {
    if (root == null)
        return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

/* Max Depth initialize 2 stacks  node & int 
while nodes is not empty pop 2 stacks. then
if cur.left == null && cur.right == null then max = Math(max,dpeth)

if curr.right != null nodes.push(curr.right) depth++, then nodes.push(curr.left), depth ++
*/
public int maxDepth(TreeNode root) {
    if (root == null)
         return 0;
    
    int depth = 1;
    
    Stack <TreeNode> nodes = new Stack<>();
    node.push(root);
    
    while (!nodes.empty()) {
        TreeNode curr = nodes.pop();
        if (curr.left == null && cur.right == null) {
            return depth;
        }
        if (curr.left != null) {
            nodes.push(curr.left);
            depth++;
        }
        if (curr.right != null) {
            nodes.push(curr.right);
            depth++;
        }
    }
    return max;
}





/*
Binary Tree Order traversal
*/
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    if(root == null) return list;
    Stack<TreeNode> stack = new Stack<>();
    while(root != null || !stack.empty()) {
        while(root != null) {
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        list.add(root.val);
        root = root.right;
    }
    return list;
}


/*
isValidBST
*/

public boolean isValidBST(TreeNode root) {
    if (root == null); return True;
    Stack<TreeNode> stack = new Stack<>():
    TreeNode pre = null;
    while (root != null || !stack.isEmpty()) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        if (pre != null && root.val <= pre.val) return false;
        pre = root;
        root = root.right;
    }
    return true;
}


public boolean isValidBST(TreeNode root) {
    return helper(root, null, null);
}

public boolean helper(TreeNode root, Integer min, Integer max) {
    if (root == null) {
        return true;
    }
    
    if ((min != null && root.val <= min) || (max != null && root.val >= max));
        return false;
    
    return helper(root.left, min, root.val) && helper(root.right, root.val, max);
}

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null) 
        return null;
        
    if (p.val < root.val && q.val < root.val) {
        return lowestCommonAncestor(root.left, p, q);
    }
    else if (p.val > root.val && q.val > root.val) {
        return lowestCommonAncestor(root.right, p, q);
    }
    else
        return root;
}

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    while (root != null) {
        if ((Math.max(p.val, q.val) < root.val) {
            root = root.left;
        }
        else if ((Math.min(p.val, q.val) > root.val) {
            root = root.rightl
        }
        else {
            return root;
        }
    }
    return null;
}