SvenStack

🧩 Problem Description

Given an integer array nums where the elements are sorted in ascending order,
convert it into a height-balanced binary search tree.

A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

💬 Example

1
2
3

Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-3,9,-10,null,5] is one possible height-balanced BST.

💡 Approach: Divide and Conquer (DFS)

• The middle element of the sorted array becomes the root.
• Recursively:
  • Left subarray → left subtree
  • Right subarray → right subtree
• This ensures the tree is balanced because each split halves the problem.

🔢 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return buildBST(nums, 0, nums.length - 1);
    }

    private TreeNode buildBST(int[] nums, int left, int right) {
        if (left > right) return null;

        int mid = left + (right - left) / 2;
        TreeNode node = new TreeNode(nums[mid]);

        node.left = buildBST(nums, left, mid - 1);
        node.right = buildBST(nums, mid + 1, right);

        return node;
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(n) — each element is processed exactly once.
• Space Complexity: O(log n) — recursion depth (balanced tree).

✍️ Summary

• Classic divide & conquer problem.
• Key to balance is picking the middle element.
• Same pattern appears in:
  • lc-109 (Sorted List to BST)
  • lc-1382 (Balance a BST)
  • lc-654 (Max Binary Tree — similar but different pivot choice)

Understanding this pattern is crucial for recursive tree construction problems.

🧩 Problem Description

Given the root of a binary tree, return the level order traversal of its nodes’ values (i.e., from left to right, level by level).

💬 Example

1
2

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

💡 Approach: Breadth-First Search (BFS)

This is a classic BFS traversal problem using a queue:

1. Start from the root and process each level of the tree.
2. For each node in the current level, push its children into the queue.
3. Collect all node values level by level.

🔢 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;

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

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

            for (int i = 0; i < size; 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);
            }

            res.add(level);
        }

        return res;
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(n) — every node is visited once
• Space Complexity: O(n) — queue + output list

✍️ Summary

• Straightforward BFS template.
• Common interview question to test level-by-level traversal.
• Often used in problems involving:
  • Tree depth
  • Zigzag/spiral level order
  • Node connect (next pointers)

Try implementing variations like lc-107, lc-103, lc-199.

🧩 Problem Description

Given the root of a binary tree, return the length of the diameter of the tree.

The diameter of a binary tree is the length of the longest path between any two nodes. This path may or may not pass through the root.

Note: The length is measured by the number of edges between nodes.

💬 Example

1
2

Input: root = [1,2,3,4,5]
Output: 3

Explanation:

• Longest path is [4 → 2 → 1 → 3], which has 3 edges.

💡 Approach: DFS with Depth Tracking

• At each node, the longest path through that node is:
  leftDepth + rightDepth
• We update a global maximum diameter during traversal.

🔢 Java Code (Recursive DFS)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    private int diameter = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        depth(root);
        return diameter;
    }

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

        int left = depth(node.left);
        int right = depth(node.right);

        // Update global diameter
        diameter = Math.max(diameter, left + right);

        return 1 + Math.max(left, right);
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(n) — visit every node once
• Space Complexity: O(h) — recursion stack, where h = height of tree

✍️ Summary

• This problem is about recognizing the non-root longest path possibility.
• Track the depths of subtrees and compute diameters along the way.
• A great example of combining DFS + global tracking.

Pattern also appears in path sum and subtree depth problems. Master it well.

🧩 Problem Description

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

💬 Example

1
2

Input: root = [1,2,2,3,4,4,3]
Output: true

Symmetric ✅

💡 Approach 1: Recursive Comparison

We define a helper function isMirror(left, right) to check whether two subtrees are mirror images of each other.

🔢 Java Code (Recursive)

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return isMirror(root.left, root.right);
    }

    private boolean isMirror(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) return true;
        if (t1 == null || t2 == null) return false;
        return (t1.val == t2.val)
            && isMirror(t1.left, t2.right)
            && isMirror(t1.right, t2.left);
    }
}

💡 Approach 2: Iterative (BFS with Queue)

We can also use a queue to compare nodes level by level.

🔢 Java Code (Iterative)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;

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

        while (!queue.isEmpty()) {
            TreeNode t1 = queue.poll();
            TreeNode t2 = queue.poll();

            if (t1 == null && t2 == null) continue;
            if (t1 == null || t2 == null) return false;
            if (t1.val != t2.val) return false;

            queue.offer(t1.left);
            queue.offer(t2.right);
            queue.offer(t1.right);
            queue.offer(t2.left);
        }

        return true;
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(n) — visit each node once
• Space Complexity:
  • Recursive: O(h)
  • Iterative: O(w) for queue

✍️ Summary

• Use recursion for elegant, clear code.
• Iterative is slightly more verbose but stack-safe.
• Understand the mirror condition:
  • left.left == right.right
  • left.right == right.left

Often paired with lc-100, lc-226, and other binary tree symmetry/mirroring problems.

🧩 Problem Description

Given the root of a binary tree, invert the tree, and return its root.

Inverting a binary tree means swapping every left and right child recursively.

💬 Example

1
2

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

💡 Approach: Recursive DFS

We recursively invert left and right subtrees, then swap them.

🔢 Java Code (Recursive)

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;

        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);

        root.left = right;
        root.right = left;

        return root;
    }
}

💡 Approach: Iterative BFS (Queue)

You can also invert using level-order traversal with a queue.

🔢 Java Code (Iterative BFS)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;

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

        while (!queue.isEmpty()) {
            TreeNode curr = queue.poll();

            // Swap left and right
            TreeNode temp = curr.left;
            curr.left = curr.right;
            curr.right = temp;

            if (curr.left != null) queue.offer(curr.left);
            if (curr.right != null) queue.offer(curr.right);
        }

        return root;
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(n) — visit every node once
• Space Complexity:
  • Recursive: O(h) (call stack)
  • Iterative: O(w) (queue width)

✍️ Summary

• Simple yet classic recursion problem.
• Test your understanding of binary tree traversal.
• Also seen in real-world scenarios like image mirror effects.

🧩 Problem Description

Given the root of a binary tree, return its maximum depth.

A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

💬 Example

1
2

Input: root = [3,9,20,null,null,15,7]
Output: 3

💡 Approach 1: Recursive DFS

We can recursively compute the depth of left and right subtrees, then take the maximum of the two.

🔢 Java Code (Recursive DFS)

1
2
3
4
5
6

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

💡 Approach 2: Iterative BFS (Level Order)

We can use a queue to perform level-order traversal and count how many levels exist.

🔢 Java Code (BFS)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;

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

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            depth++;

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

        return depth;
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(n) — visit every node once
• Space Complexity:
  • Recursive: O(h) call stack
  • BFS: O(w) for the queue (w = max width of the tree)

✍️ Summary

• Depth-first (recursive) is elegant and concise
• Level-order (BFS) gives more control (e.g., per-level info)
• Know both for interviews and practical use

Tree depth is foundational — used in balancing, recursion limits, and more.

🧩 Problem Description

Given the root of a binary tree, return its inorder traversal as a list of integers.

Inorder traversal order: left → root → right

💬 Example

1
2

Input: root = [1,null,2,3]
Output: [1,3,2]

💡 Approach 1: Recursive DFS

The simplest way is to use recursion.
Visit:

1. Left subtree
2. Current node
3. Right subtree

🔢 Java Code (Recursive)

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        dfs(root, res);
        return res;
    }

    private void dfs(TreeNode node, List<Integer> res) {
        if (node == null) return;
        dfs(node.left, res);
        res.add(node.val);
        dfs(node.right, res);
    }
}

💡 Approach 2: Iterative with Stack

Use a stack to simulate the recursion.

🔢 Java Code (Iterative)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;

        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }

            curr = stack.pop();
            res.add(curr.val);
            curr = curr.right;
        }

        return res;
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(n) — each node is visited once
• Space Complexity:
  • Recursive: O(h) stack depth (h = height)
  • Iterative: O(h) explicit stack

✍️ Summary

• Learn both recursive and iterative versions
• Foundation for tree problems like:
  • lc-144: Preorder traversal
  • lc-145: Postorder traversal
  • lc-230: Kth Smallest in BST

Tree traversal mastery is essential for any tree-based problem.

🧩 Problem Description

Design a data structure that follows the Least Recently Used (LRU) cache policy.

Implement the LRUCache class:

• LRUCache(int capacity) initializes the cache with a positive size capacity.
• int get(int key) returns the value of the key if it exists, otherwise returns -1.
• void put(int key, int value) updates the value of the key. If the number of keys exceeds the capacity, evict the least recently used key.

💬 Example

1
2
3
4
5

Input:
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1,1], [2,2], [1], [3,3], [2], [4,4], [1], [3], [4]]
Output:
[null, null, null, 1, null, -1, null, -1, 3, 4]

💡 Intuition

To achieve O(1) time complexity for both get and put, use:

• A HashMap to store key → node
• A Doubly Linked List to track the usage order
  • Most recently used at the front
  • Least recently used at the end

When a key is accessed:

• Move it to the front of the list
  When inserting:
• If at capacity, remove the tail (least recently used)

🔢 Java Code (Custom Doubly Linked List)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

class LRUCache {

    class Node {
        int key, value;
        Node prev, next;
        Node(int k, int v) {
            key = k;
            value = v;
        }
    }

    private final int capacity;
    private Map<Integer, Node> cache;
    private Node head, tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        cache = new HashMap<>();

        // Dummy head and tail
        head = new Node(0, 0);
        tail = new Node(0, 0);

        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        if (!cache.containsKey(key)) return -1;

        Node node = cache.get(key);
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        if (cache.containsKey(key)) {
            Node node = cache.get(key);
            node.value = value;
            moveToHead(node);
        } else {
            if (cache.size() == capacity) {
                Node lru = tail.prev;
                remove(lru);
                cache.remove(lru.key);
            }

            Node newNode = new Node(key, value);
            cache.put(key, newNode);
            addToHead(newNode);
        }
    }

    // Doubly Linked List helpers
    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void addToHead(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

    private void moveToHead(Node node) {
        remove(node);
        addToHead(node);
    }
}

⏱ Time and Space Complexity

• Time Complexity:
  • get: O(1)
  • put: O(1)
• Space Complexity: O(capacity)

🧠 Summary

• Combines a HashMap (for O(1) access) and a Doubly Linked List (for O(1) insert/delete).
• A great example of system design + data structure synergy.
• Common interview favorite!

Know this one cold — it’s the basis for many real-world cache systems (like Redis, in-memory caching, etc.)

🧩 Problem Description

You are given an array of k linked lists, each sorted in ascending order.

Merge all the linked lists into one sorted linked list and return it.

💬 Example

1
2

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]

💡 Approach 1: Min-Heap (Priority Queue)

Use a min-heap (priority queue) to always pull the smallest current node across all lists.

🔢 Java Code (PriorityQueue)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;

        PriorityQueue<ListNode> heap = new PriorityQueue<>(
            (a, b) -> a.val - b.val
        );

        for (ListNode node : lists) {
            if (node != null) heap.offer(node);
        }

        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;

        while (!heap.isEmpty()) {
            ListNode min = heap.poll();
            curr.next = min;
            curr = curr.next;
            if (min.next != null) heap.offer(min.next);
        }

        return dummy.next;
    }
}

⏱ Complexity (Heap Version)

• Time Complexity: O(N log k)
  • N = total number of nodes
  • k = number of lists
• Space Complexity: O(k) for the heap

💡 Approach 2: Divide and Conquer

Merge lists in pairs, just like how merge sort works.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        return merge(lists, 0, lists.length - 1);
    }

    private ListNode merge(ListNode[] lists, int left, int right) {
        if (left == right) return lists[left];
        int mid = left + (right - left) / 2;

        ListNode l1 = merge(lists, left, mid);
        ListNode l2 = merge(lists, mid + 1, right);

        return mergeTwoLists(l1, l2);
    }

    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0), curr = dummy;

        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }

        curr.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }
}

⏱ Complexity (Divide & Conquer)

• Time Complexity: O(N log k)
• Space Complexity: O(log k) due to recursion

✍️ Summary

• PriorityQueue approach is clean and uses a heap to track minimums.
• Divide & conquer approach is elegant and more space-efficient.
• Mastering this helps with:
  • lc-148 (Sort List)
  • lc-21 (Merge 2 Sorted Lists)
  • lc-218 (The Skyline Problem — heap merge concept)

Efficient merging is a key skill when working with linked lists and sorted data.

🧩 Problem Description

Given the head of a linked list, return the list sorted in ascending order.

You must sort in O(n log n) time and use constant space complexity (no array conversion).

💬 Example

1
2

Input: head = [4,2,1,3]
Output: [1,2,3,4]

💡 Intuition

We cannot use extra space like arrays. So we apply merge sort on the linked list itself:

• Split the list into halves using the slow/fast pointer technique
• Recursively sort each half
• Merge the two sorted halves (like in lc-21)

This gives us O(n log n) time and uses O(1) extra space for list nodes.

🔢 Java Code (Top-Down Merge Sort)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

class Solution {
    public ListNode sortList(ListNode head) {
        // Base case
        if (head == null || head.next == null) return head;

        // Step 1: Split list into halves
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode mid = slow.next;
        slow.next = null;

        // Step 2: Recursively sort each half
        ListNode left = sortList(head);
        ListNode right = sortList(mid);

        // Step 3: Merge sorted halves
        return merge(left, right);
    }

    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0), curr = dummy;

        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }

        curr.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(n log n)
• Space Complexity: O(log n) due to recursion stack (not extra list memory)

✍️ Summary

• Use top-down merge sort directly on the list.
• Core techniques:
  • Fast/slow pointer to find middle
  • Recursive divide-and-conquer
  • Merging two sorted linked lists
• Efficient, in-place sorting without using arrays

Make sure you’ve mastered lc-21 (merge two sorted lists) before this one — it’s the foundation of merging steps here.