SvenStack

🧩 Problem Description

Given the root of a binary tree, flatten it to a linked list in-place.
The linked list should follow the same order as a pre-order traversal.

💬 Example

1
2

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

💡 Approach 1: Reverse Preorder DFS

We can do a reverse preorder traversal (right → left → root) and keep track of the previous node to build the flattened list.

🔢 Java Code

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

class Solution {
    private TreeNode prev = null;

    public void flatten(TreeNode root) {
        if (root == null) return;
        flatten(root.right);
        flatten(root.left);
        root.right = prev;
        root.left = null;
        prev = root;
    }
}

💡 Approach 2: Iterative with Stack

We can also simulate preorder traversal using a stack and rearrange pointers.

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

class Solution {
    public void flatten(TreeNode root) {
        if (root == null) return;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode curr = stack.pop();

            if (curr.right != null) stack.push(curr.right);
            if (curr.left != null) stack.push(curr.left);

            if (!stack.isEmpty()) {
                curr.right = stack.peek();
            }
            curr.left = null;
        }
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(n) — visiting all nodes once.
• Space Complexity: O(h) for recursion / stack (O(n) in worst case).

✍️ Summary

• Reverse preorder DFS is a neat trick because it avoids extra temporary storage.
• Iterative stack solution is more explicit and easier to debug.
• Related problems:
  • lc-116 — Populating Next Right Pointers in Each Node
  • lc-430 — Flatten a Multilevel Doubly Linked List

🧩 Problem Description

Given the root of a binary tree, imagine you are standing on the right side of it.
Return the values of the nodes you can see ordered from top to bottom.

💬 Example

1
2

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

1
2

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

1
2

Input: root = []
Output: []

💡 Approach 1: BFS (Level Order Traversal)

We can perform a level-order traversal and take the last node at each level as the visible node from the right side.

🔢 Java Code

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

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

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

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (i == size - 1) { // last node in this level
                    result.add(node.val);
                }
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }
        return result;
    }
}

💡 Approach 2: DFS (Right-First Preorder)

We can also use DFS, always visiting right child first so the first node we encounter at each depth is the visible one.

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

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

    private void dfs(TreeNode node, int depth, List<Integer> result) {
        if (node == null) return;
        if (depth == result.size()) {
            result.add(node.val);
        }
        dfs(node.right, depth + 1, result);
        dfs(node.left, depth + 1, result);
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(n) — Each node is visited once.
• Space Complexity: O(h) — h is the height of the tree (O(n) worst case).

✍️ Summary

• BFS is intuitive and level-based.
• DFS (right-first) is memory-friendly and elegant.
• This problem pairs well with:
  • lc-102 — Binary Tree Level Order Traversal
  • lc-103 — Zigzag Level Order Traversal

🧩 Problem Description

Given the root of a binary search tree (BST) and an integer k, return the kth smallest value (1-indexed) in the BST.

💬 Example

1
2

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

1
2

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

💡 Approach 1: Inorder Traversal (Iterative)

A BST’s inorder traversal produces nodes in sorted order.
We can simply traverse in-order and stop when we reach the k-th node.

🔢 Java Code

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

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        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();
            if (--k == 0) return curr.val;
            curr = curr.right;
        }
        return -1; // should not reach here if k is valid
    }
}

💡 Approach 2: Recursive Inorder Traversal

We can also use recursion with a counter to track when we reach the k-th element.

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

class Solution {
    private int count = 0;
    private int result = 0;

    public int kthSmallest(TreeNode root, int k) {
        inorder(root, k);
        return result;
    }

    private void inorder(TreeNode node, int k) {
        if (node == null) return;
        inorder(node.left, k);
        count++;
        if (count == k) {
            result = node.val;
            return;
        }
        inorder(node.right, k);
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(h + k) — h is tree height; in the worst case O(n) if tree is unbalanced.
• Space Complexity: O(h) for stack/recursion.

✍️ Summary

• Inorder traversal is perfect for BST because it gives sorted order.
• For large trees with many queries, consider augmenting each node with subtree size to get O(log n) queries.
• Related problems:
  • lc-98 — Validate BST
  • lc-701 — Insert into BST
  • lc-450 — Delete Node in BST

🧩 Problem Description

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as:

• The left subtree of a node contains only nodes with values less than the node’s value.
• The right subtree of a node contains only nodes with values greater than the node’s value.
• Both the left and right subtrees must also be valid BSTs.

💬 Example

1
2

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

1
2
3

Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The value 3 is in the right subtree of 5 but is less than 5.

💡 Approach 1: DFS with Value Ranges

We recursively check each node’s value against an allowed range:

1. Initially, the root has range (-∞, +∞).
2. For left child: upper bound is parent’s value.
3. For right child: lower bound is parent’s value.
4. If any node violates the range rule, it’s not a BST.

🔢 Java Code

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

class Solution {
    public boolean isValidBST(TreeNode root) {
        return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean validate(TreeNode node, long min, long max) {
        if (node == null) return true;
        if (node.val <= min || node.val >= max) return false;

        return validate(node.left, min, node.val) &&
               validate(node.right, node.val, max);
    }
}

💡 Approach 2: Inorder Traversal Check

• Perform inorder traversal of the tree.
• If the resulting sequence is strictly increasing, it’s a valid BST.

🔢 Java Code

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

class Solution {
    private long prev = Long.MIN_VALUE;

    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        if (!isValidBST(root.left)) return false;
        if (root.val <= prev) return false;
        prev = root.val;
        return isValidBST(root.right);
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(n) — every node visited once.
• Space Complexity: O(h) — recursion depth (h is tree height).

✍️ Summary

• Range-check DFS is the most intuitive and avoids extra storage.
• Inorder traversal works because BST’s inorder is sorted.
• Common BST pitfalls:
  • Duplicate values — BST usually disallows duplicates.
  • Only checking immediate children is not enough — must check whole range.

Related problems: lc-230 (Kth Smallest in BST), lc-701 (Insert into BST), lc-450 (Delete Node in BST)

🧩 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.