Trees

Definition

---

Tree Types

---

Big O Complexity

---

When to Use

---

Binary Search Tree Implementation

public class BST<T extends Comparable<T>> {

    class TreeNode {
        T val;
        TreeNode left, right;
        TreeNode(T val) { this.val = val; }
    }

    private TreeNode root;

    // Insert - O(log n) average
    public void insert(T val) {
        root = insertRec(root, val);
    }

    private TreeNode insertRec(TreeNode node, T val) {
        if (node == null) return new TreeNode(val);

        if (val.compareTo(node.val) < 0) {
            node.left = insertRec(node.left, val);
        } else if (val.compareTo(node.val) > 0) {
            node.right = insertRec(node.right, val);
        }
        return node;
    }

    // Search - O(log n) average
    public boolean search(T val) {
        return searchRec(root, val);
    }

    private boolean searchRec(TreeNode node, T val) {
        if (node == null) return false;
        if (val.equals(node.val)) return true;

        return val.compareTo(node.val) < 0
            ? searchRec(node.left, val)
            : searchRec(node.right, val);
    }

    // Delete - O(log n) average
    public void delete(T val) {
        root = deleteRec(root, val);
    }

    private TreeNode deleteRec(TreeNode node, T val) {
        if (node == null) return null;

        if (val.compareTo(node.val) < 0) {
            node.left = deleteRec(node.left, val);
        } else if (val.compareTo(node.val) > 0) {
            node.right = deleteRec(node.right, val);
        } else {
            // Node to delete found
            if (node.left == null) return node.right;
            if (node.right == null) return node.left;

            // Two children: get in-order successor
            node.val = findMin(node.right);
            node.right = deleteRec(node.right, node.val);
        }
        return node;
    }

    private T findMin(TreeNode node) {
        while (node.left != null) node = node.left;
        return node.val;
    }

    // Traversals
    public void inorder(TreeNode node, List<T> result) {
        if (node == null) return;
        inorder(node.left, result);
        result.add(node.val);
        inorder(node.right, result);
    }

    public void preorder(TreeNode node, List<T> result) {
        if (node == null) return;
        result.add(node.val);
        preorder(node.left, result);
        preorder(node.right, result);
    }

    public void postorder(TreeNode node, List<T> result) {
        if (node == null) return;
        postorder(node.left, result);
        postorder(node.right, result);
        result.add(node.val);
    }

    // Level-order (BFS)
    public List<List<T>> levelOrder() {
        List<List<T>> result = new ArrayList<>();
        if (root == null) return result;

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

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<T> level = new ArrayList<>();

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            result.add(level);
        }
        return result;
    }
}

---

Heap Implementation

public class MinHeap {
    private int[] heap;
    private int size;
    private int capacity;

    public MinHeap(int capacity) {
        this.capacity = capacity;
        this.heap = new int[capacity];
        this.size = 0;
    }

    private int parent(int i) { return (i - 1) / 2; }
    private int leftChild(int i) { return 2 * i + 1; }
    private int rightChild(int i) { return 2 * i + 2; }

    // Insert - O(log n)
    public void insert(int val) {
        if (size == capacity) resize();
        heap[size] = val;
        heapifyUp(size);
        size++;
    }

    // Extract min - O(log n)
    public int extractMin() {
        if (size == 0) throw new NoSuchElementException();
        int min = heap[0];
        heap[0] = heap[size - 1];
        size--;
        heapifyDown(0);
        return min;
    }

    // Peek - O(1)
    public int peek() {
        if (size == 0) throw new NoSuchElementException();
        return heap[0];
    }

    private void heapifyUp(int i) {
        while (i > 0 && heap[parent(i)] > heap[i]) {
            swap(i, parent(i));
            i = parent(i);
        }
    }

    private void heapifyDown(int i) {
        int smallest = i;
        int left = leftChild(i);
        int right = rightChild(i);

        if (left < size && heap[left] < heap[smallest]) smallest = left;
        if (right < size && heap[right] < heap[smallest]) smallest = right;

        if (smallest != i) {
            swap(i, smallest);
            heapifyDown(smallest);
        }
    }

    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    private void resize() {
        capacity *= 2;
        heap = Arrays.copyOf(heap, capacity);
    }
}

// Using Java's PriorityQueue
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

---

Trie Implementation

public class Trie {

    private class TrieNode {
        Map<Character, TrieNode> children = new HashMap<>();
        boolean isEndOfWord = false;
    }

    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    // Insert - O(m)
    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            node.children.putIfAbsent(c, new TrieNode());
            node = node.children.get(c);
        }
        node.isEndOfWord = true;
    }

    // Search - O(m)
    public boolean search(String word) {
        TrieNode node = findNode(word);
        return node != null && node.isEndOfWord;
    }

    // Prefix search - O(m)
    public boolean startsWith(String prefix) {
        return findNode(prefix) != null;
    }

    private TrieNode findNode(String str) {
        TrieNode node = root;
        for (char c : str.toCharArray()) {
            if (!node.children.containsKey(c)) return null;
            node = node.children.get(c);
        }
        return node;
    }

    // Get all words with prefix
    public List<String> getWordsWithPrefix(String prefix) {
        List<String> result = new ArrayList<>();
        TrieNode node = findNode(prefix);
        if (node != null) {
            collectWords(node, new StringBuilder(prefix), result);
        }
        return result;
    }

    private void collectWords(TrieNode node, StringBuilder current, List<String> result) {
        if (node.isEndOfWord) {
            result.add(current.toString());
        }
        for (Map.Entry<Character, TrieNode> entry : node.children.entrySet()) {
            current.append(entry.getKey());
            collectWords(entry.getValue(), current, result);
            current.deleteCharAt(current.length() - 1);
        }
    }
}

---

Common Tree Problems

Validate BST

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

private boolean isValidBST(TreeNode node, Integer min, Integer max) {
    if (node == null) return true;
    if (min != null && node.val <= min) return false;
    if (max != null && node.val >= max) return false;
    return isValidBST(node.left, min, node.val) &&
           isValidBST(node.right, node.val, max);
}

Lowest Common Ancestor

// For BST
public TreeNode lowestCommonAncestorBST(TreeNode root, TreeNode p, TreeNode q) {
    while (root != null) {
        if (p.val < root.val && q.val < root.val) {
            root = root.left;
        } else if (p.val > root.val && q.val > root.val) {
            root = root.right;
        } else {
            return root;
        }
    }
    return null;
}

// For Binary Tree
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;

    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);

    if (left != null && right != null) return root;
    return left != null ? left : right;
}

Maximum Depth / Height

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

Check if Balanced

public boolean isBalanced(TreeNode root) {
    return checkHeight(root) != -1;
}

private int checkHeight(TreeNode node) {
    if (node == null) return 0;

    int left = checkHeight(node.left);
    if (left == -1) return -1;

    int right = checkHeight(node.right);
    if (right == -1) return -1;

    if (Math.abs(left - right) > 1) return -1;
    return 1 + Math.max(left, right);
}

Serialize/Deserialize BST

public String serialize(TreeNode root) {
    StringBuilder sb = new StringBuilder();
    serializeHelper(root, sb);
    return sb.toString();
}

private void serializeHelper(TreeNode node, StringBuilder sb) {
    if (node == null) {
        sb.append("null,");
        return;
    }
    sb.append(node.val).append(",");
    serializeHelper(node.left, sb);
    serializeHelper(node.right, sb);
}

public TreeNode deserialize(String data) {
    Queue<String> queue = new LinkedList<>(Arrays.asList(data.split(",")));
    return deserializeHelper(queue);
}

private TreeNode deserializeHelper(Queue<String> queue) {
    String val = queue.poll();
    if (val.equals("null")) return null;

    TreeNode node = new TreeNode(Integer.parseInt(val));
    node.left = deserializeHelper(queue);
    node.right = deserializeHelper(queue);
    return node;
}

Top K Frequent Elements (Heap)

public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> count = new HashMap<>();
    for (int num : nums) {
        count.merge(num, 1, Integer::sum);
    }

    PriorityQueue<Integer> heap = new PriorityQueue<>(
        (a, b) -> count.get(a) - count.get(b)
    );

    for (int num : count.keySet()) {
        heap.offer(num);
        if (heap.size() > k) heap.poll();
    }

    return heap.stream().mapToInt(i -> i).toArray();
}

---

Pros and Cons

---

Java Collections

// TreeMap - Red-Black Tree (balanced BST)
TreeMap<Integer, String> treeMap = new TreeMap<>();
treeMap.put(5, "five");
treeMap.firstKey();           // Smallest key
treeMap.lastKey();            // Largest key
treeMap.floorKey(4);          // Largest key ≤ 4
treeMap.ceilingKey(4);        // Smallest key ≥ 4
treeMap.lowerKey(4);          // Largest key < 4
treeMap.higherKey(4);         // Smallest key > 4
treeMap.subMap(2, 8);         // Keys in range [2, 8)

// TreeSet - Red-Black Tree Set
TreeSet<Integer> treeSet = new TreeSet<>();
treeSet.add(5);
treeSet.first();              // Smallest
treeSet.last();               // Largest
treeSet.floor(4);             // Largest ≤ 4
treeSet.ceiling(4);           // Smallest ≥ 4

// PriorityQueue - Binary Heap
PriorityQueue<Integer> pq = new PriorityQueue<>();

---