Problem 1: Binary Tree Right Side View

Link to the problem: https://leetcode.com/problems/binary-tree-right-side-view/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;

        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);

        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode current = q.poll();
                if (i == size - 1) result.add(current.val);
                if (current.left != null) q.offer(current.left);
                if (current.right != null) q.offer(current.right);
            }
        }

        return result;
    }
}

---

Problem 2: Insert Delete GetRandom O(1)

Link to the problem: https://leetcode.com/problems/insert-delete-getrandom-o1/

class RandomizedSet {

    HashMap<Integer, Integer> map;
    List<Integer> list = new ArrayList<>();

    public RandomizedSet() {
        map = new HashMap<>();
    }

    public boolean insert(int val) {
        if(map.containsKey(val))
            return false;
        map.put(val, 1);
        list.add(val);
        return true;
    }

    public boolean remove(int val) {
        if(map.containsKey(val)){
            map.remove(val);
            list.remove((Integer) val);
            return true;
        }
        return false;
    }

    public int getRandom() {
        int randomNumber = 0 + (int)(Math.random() * ((list.size()-1) + 1));
        return list.get(randomNumber);
    }
}

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet obj = new RandomizedSet();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */

---

Problem 3: First Missing Positive

Link to the problem: https://leetcode.com/problems/first-missing-positive/

class Solution {
    public int firstMissingPositive(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int max = Integer.MIN_VALUE;
        for(int i:nums){
            if(i>=0 && !map.containsKey(i)) map.put(i, 1);
            max = max>i?max:i;
        }
        if(max<1) return 1;
        for(int i=1; i<max; i++)
            if(!map.containsKey(i)) return i;
        return max+1;
    }
}

---

Problem 4: Validate BST

Link to the problem: https://leetcode.com/problems/validate-binary-search-tree/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        return valid(root, Long.MIN_VALUE, Long.MAX_VALUE);        
    }

    private boolean valid(TreeNode node, long minimum, long maximum) {
        if (node == null) return true;
        if (!(node.val > minimum && node.val < maximum)) return false;
        return valid(node.left, minimum, node.val) && valid(node.right, node.val, maximum);
    }    
}

---

Problem 5: Kth Smallest Element in a BST

Link to the problem: https://leetcode.com/problems/kth-smallest-element-in-a-bst/

class Solution {
    int count = 0;
    TreeNode result = null;

    public int kthSmallest(TreeNode root, int k) {
        helper(root, k);
        return result.val;
    }

    private void helper(TreeNode node, int k) {
        if(node == null) return;

        helper(node.left, k);
        count++;
        if(count == k) {
            result = node;
            return;
        }
        helper(node.right, k);
    }
}

---