Home/DSA Complete from Scratch to Expert/dsa-topics

Trees

Master this topic with zero to advance depth.

Invert Binary Tree

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

Easy

Examples

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

Approach 1

Level I: Recursive DFS

Intuition

To invert a binary tree, we swap the left and right children of every node. This can be done recursively: swap children of the current node, then recurse into both subtrees.

⏱ O(N)💾 O(H)

Detailed Dry Run

root = [4,2,7] -> Swap(2,7) -> [4,7,2]. Recurse into subtrees.

java

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        TreeNode temp = root.left;
        root.left = invertTree(root.right);
        root.right = invertTree(temp);
        return root;
    }
}

Approach 2

Level II: Iterative BFS (Queue)

Intuition

Process the tree level by level. Use a queue to store nodes. For each node, swap its children and add them to the queue if they exist.

⏱ O(N)💾 O(W)

Detailed Dry Run

Queue: [4]. Pop 4, swap(2,7), Queue: [7,2]. Pop 7, swap(6,9)...

java

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            TreeNode temp = node.left;
            node.left = node.right;
            node.right = temp;
            if (node.left != null) q.add(node.left);
            if (node.right != null) q.add(node.right);
        }
        return root;
    }
}

Approach 3

Level III: Iterative DFS (Stack)

Intuition

Similar to BFS, but use a stack. The order of traversal doesn't change the fact that every node's children need to be swapped.

Diagram

(1) Swap children of Root    (2) Result after subtrees
      4                          4
     / \                        / \
    2   7                      7   2
   / \ / \                    / \ / \
  1  3 6  9                  9  6 3  1

⏱ O(N)💾 O(H)

Detailed Dry Run

Stack: [4]. Pop 4, swap(2,7), Push(2,7). Pop 7, swap(6,9)... mirrored tree.

java

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            TreeNode temp = node.left;
            node.left = node.right;
            node.right = temp;
            if (node.left != null) stack.push(node.left);
            if (node.right != null) stack.push(node.right);
        }
        return root;
    }
}

Maximum Depth of Binary Tree

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

Easy

Examples

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

Approach 1

Level I: Recursive DFS (Post-order)

Intuition

Max depth is $1 + \max(\text{depth of left child}, \text{depth of right child})$ . This naturally fits recursion.

⏱ O(N)💾 O(H)

Detailed Dry Run

root(3) -> 1 + max(depth(9), depth(20)). depth(9)=1, depth(20)=2. Result = 3.

java

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

Approach 2

Level II: Iterative BFS (Level Order)

Intuition

Traverse the tree level by level. Every completed level increases the depth.

Diagram

Level 1: [3] -> Depth 1
Level 2: [9, 20] -> Depth 2
Level 3: [15, 7] -> Depth 3

⏱ O(N)💾 O(W)

Detailed Dry Run

Queue: [3]. size=1. Pop 3, push 9,20. depth=1. Queue: [9,20]. size=2. Pop both, push 15,7. depth=2. Final depth=3.

java

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        int depth = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            depth++;
            for (int i = 0; i < size; i++) {
                TreeNode node = q.poll();
                if (node.left != null) q.add(node.left);
                if (node.right != null) q.add(node.right);
            }
        }
        return depth;
    }
}

Approach 3

Level III: Iterative DFS (Stack)

Intuition

Manually manage a stack to mimic recursion. Store pairs of (node, depth) to keep track of max depth.

⏱ O(N)💾 O(H)

Detailed Dry Run

Stack: [(3,1)]. Pop (3,1), Max=1. Push (20,2), (9,2). Pop (9,2), Max=2. Pop (20,2), Push(7,3), (15,3). Pop (15,3), Max=3.

java

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        Stack<Pair<TreeNode, Integer>> stack = new Stack<>();
        stack.push(new Pair<>(root, 1));
        int maxDepth = 0;
        while (!stack.isEmpty()) {
            Pair<TreeNode, Integer> curr = stack.pop();
            TreeNode node = curr.getKey();
            int d = curr.getValue();
            maxDepth = Math.max(maxDepth, d);
            if (node.left != null) stack.push(new Pair<>(node.left, d + 1));
            if (node.right != null) stack.push(new Pair<>(node.right, d + 1));
        }
        return maxDepth;
    }
}

Same Tree

Given roots of two trees p and q, check if they are the same.

Easy

Examples

Input: p = [1,2,3], q = [1,2,3]
Output: true

Approach 1

Level I: Recursive DFS

Intuition

Two trees are identical if their roots match and their respective subtrees are identical.

Diagram

(1) p.val == q.val?
(2) isSameTree(p.left, q.left)
(3) isSameTree(p.right, q.right)

⏱ O(N)💾 O(H)

Detailed Dry Run

p(1), q(1) -> match. Recurse(2,2) -> match. Recurse(3,3) -> match. Result = true.

java

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if (p == null || q == null || p.val != q.val) return false;
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

Approach 2

Level III: Iterative BFS (Parallel Queue)

Intuition

Use a queue to process pairs of nodes from both trees. If any pair differs, trees are not identical.

⏱ O(N)💾 O(W)

Detailed Dry Run

Queue: [(p, q)]. Pop, compare. Push children pairs. Any mismatch -> false.

java

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(p); queue.add(q);
        while (!queue.isEmpty()) {
            TreeNode n1 = queue.poll(), n2 = queue.poll();
            if (n1 == null && n2 == null) continue;
            if (n1 == null || n2 == null || n1.val != n2.val) return false;
            queue.add(n1.left); queue.add(n2.left);
            queue.add(n1.right); queue.add(n2.right);
        }
        return true;
    }
}

Symmetric Tree

Check if a tree is a mirror of itself.

Easy

Examples

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

Approach 1

Level I: Recursive DFS

Intuition

A tree is symmetric if its left and right subtrees are mirrors of each other. Two trees t1 and t2 are mirrors if:

Their roots have the same value.
t1.left is a mirror of t2.right.
t1.right is a mirror of t2.left.

⏱ O(N)💾 O(H)

Detailed Dry Run

Mirror(L, R) -> L.val == R.val && Mirror(L.left, R.right) && Mirror(L.right, R.left).

java

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

Approach 2

Level II: Iterative BFS (Queue)

Intuition

Use a queue to process nodes in pairs. Each pair contains nodes that should be mirrors of each other. For a root, we push (root.left, root.right).

Diagram

(1) Queue: [1.L, 1.R] -> [2, 2]
(2) Pop pair (2, 2), Push pairs: [(2.L, 2.R), (2.R, 2.L)] -> [3, 3, 4, 4]

⏱ O(N)💾 O(W)

Detailed Dry Run

Queue: [2, 2]. Pop 2, 2. Push 3(L), 3(R) and 4(R), 4(L). Queue: [3, 3, 4, 4]. All match -> true.

java

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root.left); q.add(root.right);
        while (!q.isEmpty()) {
            TreeNode t1 = q.poll(), t2 = q.poll();
            if (t1 == null && t2 == null) continue;
            if (t1 == null || t2 == null || t1.val != t2.val) return false;
            q.add(t1.left); q.add(t2.right);
            q.add(t1.right); q.add(t2.left);
        }
        return true;
    }
}

Approach 3

Level III: Iterative DFS (Two Stacks)

Intuition

Process the tree in parallel using two stacks. One stack follows Left -> Right and the other follows Right -> Left. Their values and structure must match at every step.

⏱ O(N)💾 O(H)

Detailed Dry Run

Stack1: [L], Stack2: [R]. Pop both, compare. Push L1.left, R1.right and L1.right, R1.left to respective stacks.

java

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        Stack<TreeNode> s1 = new Stack<>(), s2 = new Stack<>();
        s1.push(root.left); s2.push(root.right);
        while (!s1.isEmpty()) {
            TreeNode n1 = s1.pop(), n2 = s2.pop();
            if (n1 == null && n2 == null) continue;
            if (n1 == null || n2 == null || n1.val != n2.val) return false;
            s1.push(n1.left); s2.push(n2.right);
            s1.push(n1.right); s2.push(n2.left);
        }
        return true;
    }
}

Subtree of Another Tree

Check if a tree subRoot is a subtree of root.

Easy

Examples

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

Approach 1

Level I: Recursive DFS (Is Match?)

Intuition

A tree s is a subtree of t if:

s and t are identical.
s is a subtree of t.left.
s is a subtree of t.right.

⏱ O(M * N) (where M, N are nodes in each tree)💾 O(H)

Detailed Dry Run

root(3) != sub(4). check root(4) == sub(4) -> YES (IsSameTree).

java

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) return false;
        if (isSame(root, subRoot)) return true;
        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }
    private boolean isSame(TreeNode s, TreeNode t) {
        if (s == null && t == null) return true;
        if (s == null || t == null || s.val != t.val) return false;
        return isSame(s.left, t.left) && isSame(s.right, t.right);
    }
}

Approach 2

Level II: Preorder String Matching (O(N))

Intuition

Serialize both trees into strings using preorder traversal. Add special markers for null nodes (e.g., '#') and separate values to avoid ambiguity (e.g., ','). If the serialized subRoot is a substring of serialized root, it's a subtree.

Diagram

Tree: 3(4,5) -> Preorder: ",3,4,#,#,5,#,#"
Subtree: 4 -> Preorder: ",4,#,#"
Match found in ",3,4,#,#,5,#,#"!

⏱ O(N + M)💾 O(N + M)

Detailed Dry Run

Serialize root: ^3,4,1,#,#,2,#,#,5,#,#. Serialize sub: ^4,1,#,#,2,#,#. Sub exists in Root -> True.

java

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        String r = serialize(root);
        String s = serialize(subRoot);
        return r.contains(s);
    }
    private String serialize(TreeNode node) {
        if (node == null) return ",#";
        return "," + node.val + serialize(node.left) + serialize(node.right);
    }
}

Diameter of Binary Tree

Find the length of the longest path between any two nodes in a tree.

Easy

Examples

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

Approach 1

Level I: Recursive DFS (Bottom-Up)

Intuition

The diameter of a tree at node $N$ is the maximum of:

Depth of Left Subtree + Depth of Right Subtree.
Diameter of Left Subtree.
Diameter of Right Subtree. Using a bottom-up approach, we can calculate height and track the max diameter simultaneously.

⏱ O(N)💾 O(H)

Detailed Dry Run

Node(2): Left height=1, Right height=1. Diameter = 2. Max = 2. Return height=2.

java

class Solution {
    int max = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        height(root);
        return max;
    }
    private int height(TreeNode node) {
        if (node == null) return 0;
        int l = height(node.left), r = height(node.right);
        max = Math.max(max, l + r);
        return 1 + Math.max(l, r);
    }
}

Approach 2

Level II: Recursive Bottom-Up (Pair Result)

Intuition

Instead of using a global variable, each recursive call returns a pair: (height, diameter_so_far). This is a cleaner functional approach.

Diagram

Node(2) returns {Height: 2, Diameter: 2}
Node(3) returns {Height: 1, Diameter: 0}
Root(1) calc: max(2.H+3.H, 2.D, 3.D) -> max(3, 2, 0) = 3.

⏱ O(N)💾 O(H)

Detailed Dry Run

DFS returns {h, d}. For null: {0, 0}. For leaf: {1, 0}. For 2: l={1,0}, r={1,0} -> {2, 2}. Final root returns {max_h, max_d}.

java

class Solution {
    public int diameterOfBinaryTree(TreeNode root) {
        return dfs(root)[1];
    }
    private int[] dfs(TreeNode node) {
        if (node == null) return new int[]{0, 0};
        int[] l = dfs(node.left), r = dfs(node.right);
        int h = 1 + Math.max(l[0], r[0]);
        int d = Math.max(l[1], Math.max(r[1], l[0] + r[0]));
        return new int[]{h, d};
    }
}

Approach 3

Level III: Optimal (Iterative Post-order)

Intuition

We can solve this iteratively by performing a Post-order traversal using a stack. We keep a Map to store the heights of nodes as we finish processing them. For each node, diameter = height(left) + height(right).

Logic

Use a stack for post-order.
Store computed heights in Map<TreeNode, Integer>.
height = 1 + max(h_left, h_right).
diameter = h_left + h_right.

⏱ O(N)💾 O(N)

Detailed Dry Run

Stack processes leaves first, populating Map(leaf) = 1. Then Parent(2) sees l=1, r=1, Map(2)=2, MaxD=2. Root(1) sees Map(2)=2, Map(3)=1, MaxD=max(2, 3)=3.

java

public class Main {
    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        int maxD = 0;
        Map<TreeNode, Integer> map = new HashMap<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root, last = null;
        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                stack.push(curr);
                curr = curr.left;
            } else {
                TreeNode peek = stack.peek();
                if (peek.right != null && last != peek.right) {
                    curr = peek.right;
                } else {
                    TreeNode node = stack.pop();
                    int l = map.getOrDefault(node.left, 0);
                    int r = map.getOrDefault(node.right, 0);
                    maxD = Math.max(maxD, l + r);
                    map.put(node, 1 + Math.max(l, r));
                    last = node;
                }
            }
        }
        return maxD;
    }
}

Balanced Binary Tree

Check if a tree is height-balanced.

Easy

Examples

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

Approach 1

Level I: Recursive DFS (Top-Down)

Intuition

For each node, compute the height of its left and right subtrees. If the difference is $> 1$ , it's not balanced. Then recurse for both children.

⏱ O(N^2)💾 O(H)

Detailed Dry Run

root(3): H(L)=1, H(R)=2. Diff=1. OK. Recurse(9) and Recurse(20).

java

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        int lh = height(root.left), rh = height(root.right);
        return Math.abs(lh - rh) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }
    private int height(TreeNode node) {
        if (node == null) return 0;
        return 1 + Math.max(height(node.left), height(node.right));
    }
}

Approach 2

Level II: Recursive with Memoization

Intuition

To optimize the $O(N^2)$ approach, we can cache the height of each node in a HashMap. This ensures that we only calculate the height of each node once, bringing the complexity down to $O(N)$ .

Logic

Use a Map to store node -> height.
In height(node), return map value if present.
Recurse for balanced property using cached heights.

⏱ O(N)💾 O(N)

Detailed Dry Run

Map: {9:1, 15:1, 7:1, 20:2, 3:3}. Heights are fetched from Map in O(1) during balance check.

java

public class Main {
    Map<TreeNode, Integer> map = new HashMap<>();
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }
    private int height(TreeNode node) {
        if (node == null) return 0;
        if (map.containsKey(node)) return map.get(node);
        int h = 1 + Math.max(height(node.left), height(node.right));
        map.put(node, h);
        return h;
    }
}

Approach 3

Level III: Optimal (Bottom-Up DFS)

Intuition

Compute heights bottom-up. If any subtree is unbalanced, return -1 to signal failure to parents immediately.

⏱ O(N)💾 O(H)

Detailed Dry Run

Node(20): L=1, R=1 -> height=2. root(3): L=1, R=2 -> height=3. Balanced.

java

class Solution {
    public boolean isBalanced(TreeNode root) {
        return height(root) != -1;
    }
    private int height(TreeNode node) {
        if (node == null) return 0;
        int lh = height(node.left); if (lh == -1) return -1;
        int rh = height(node.right); if (rh == -1) return -1;
        if (Math.abs(lh - rh) > 1) return -1;
        return 1 + Math.max(lh, rh);
    }
}

Construct Binary Tree from Preorder and Inorder Traversal

Rebuild tree.

Medium

Approach 1

Level I: Recursive with Linear Search

Intuition

To reconstruct a binary tree from preorder and inorder traversals, we use the fact that the first element in preorder is always the root. We then find this root in the inorder traversal. Everything to the left of the root in inorder belongs to the left subtree, and everything to the right belongs to the right subtree.

Thought Process

root = preorder[0].
Find root index in inorder by iterating (Linear Search).
Slice inorder into leftInorder and rightInorder.
Recursively build left and right subtrees.

⏱ O(N^2) (Search takes O(N) for each of N nodes)💾 O(N) (Recursion stack and array slicing)

Detailed Dry Run

Preorder	Inorder	Root	Left Subtree	Right Subtree
[3,9,20]	[9,3,20]	3	[9]	[20]

java

import java.util.*;

public class Main {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return helper(0, 0, inorder.length - 1, preorder, inorder);
    }

    private TreeNode helper(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder) {
        if (preStart > preorder.length - 1 || inStart > inEnd) return null;
        TreeNode root = new TreeNode(preorder[preStart]);
        int inIndex = 0;
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == root.val) inIndex = i;
        }
        root.left = helper(preStart + 1, inStart, inIndex - 1, preorder, inorder);
        root.right = helper(preStart + inIndex - inStart + 1, inIndex + 1, inEnd, preorder, inorder);
        return root;
    }

    public static void main(String[] args) {
        int[] pre = {3, 9, 20, 15, 7}, in = {9, 3, 15, 20, 7};
        TreeNode root = new Main().buildTree(pre, in);
        System.out.println(root.val); // 3
    }
}

Approach 2

Level II: Iterative with Stack

Intuition

We can build the tree iteratively using a stack. The first element of preorder is the root. For subsequent elements, if a node is a left child, it follows its parent in preorder. If it's a right child, it follows some ancestor's left subtree completion.

Logic

Push root to stack.
For each next value: If stack.top().val != inorder[inIndex], it's a left child.
Else, pop from stack until stack.top().val != inorder[inIndex] to find the parent whose right child this value is.

⏱ O(N)💾 O(N)

Detailed Dry Run

Pre:[3,9,20], In:[9,3,20]. Push 3. 3!=9 -> 9 is 3.left. Push 9. 9==9 -> Pop 9, Pop 3. Next is 20. 20 is 3.right.

java

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0) return null;
        TreeNode root = new TreeNode(preorder[0]);
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        int inIndex = 0;
        for (int i = 1; i < preorder.length; i++) {
            TreeNode node = stack.peek();
            if (node.val != inorder[inIndex]) {
                node.left = new TreeNode(preorder[i]);
                stack.push(node.left);
            } else {
                while (!stack.isEmpty() && stack.peek().val == inorder[inIndex]) {
                    node = stack.pop();
                    inIndex++;
                }
                node.right = new TreeNode(preorder[i]);
                stack.push(node.right);
            }
        }
        return root;
    }
}

Approach 3

Level III: Optimal (Recursive with Hash Map)

Intuition

Thought Process

Linear search for the root in the inorder array is the primary bottleneck ( $O(N)$ per call). We can optimize this by pre-processing the inorder array into a Hash Map that stores value -> index. This reduces the lookup time to $O(1)$ .

Diagram

Pre: [3, 9, 20, 15, 7]
In:  [9, 3, 15, 20, 7]
Map: {9:0, 3:1, 15:2, 20:3, 7:4}

Step 1: Root = 3 (Index 1 in Inorder)
Left Inorder: [0..0], Right Inorder: [2..4]

⏱ O(N) (Pre-processing takes O(N), every node built in O(1))💾 O(N) (Map stores N elements, recursion stack O(H))

Detailed Dry Run

Call	Range (Start, End)	Root Val	Map Index
Main	(0, 4)	3	1
Left	(0, 0)	9	0
Right	(2, 4)	20	3

java

public class Main {
    int preIndex = 0;
    Map<Integer, Integer> inMap = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) inMap.put(inorder[i], i);
        return helper(preorder, 0, inorder.length - 1);
    }
    private TreeNode helper(int[] preorder, int left, int right) {
        if (left > right) return null;
        int rootVal = preorder[preIndex++];
        TreeNode root = new TreeNode(rootVal);
        root.left = helper(preorder, left, inMap.get(rootVal) - 1);
        root.right = helper(preorder, inMap.get(rootVal) + 1, right);
        return root;
    }
}

⚠️ Common Pitfalls & Tips

Ensure preIndex is accessed globally or passed correctly across recursive calls. Using array slicing (like preorder[1:mid+1]) is easier but often $O(N^2)$ in languages like Python due to copy overhead.

Validate Binary Search Tree

Is valid BST?

Medium

Approach 1

Level I: Inorder to Array

Intuition

A Binary Search Tree has a unique property: its inorder traversal (Left, Root, Right) produces a strictly increasing sequence of values. We can perform an inorder traversal, store the results in an array, and then check if the array is sorted and contains no duplicates.

Thought Process

Perform DFS (Inorder).
Store every node.val in a list.
Iterate through the list and check if list[i] < list[i+1].

⏱ O(N)💾 O(N) (to store the array)

Detailed Dry Run

Node	Left Subtree	Right Subtree	Array
2	[1]	[3]	[1, 2, 3]
Result			Valid BST!

java

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Main {
    public boolean isValidBST(TreeNode root) {
        List<Integer> nodes = new ArrayList<>();
        inorder(root, nodes);
        for (int i = 0; i < nodes.size() - 1; i++) {
            if (nodes.get(i) >= nodes.get(i + 1)) return false;
        }
        return true;
    }

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

    public static void main(String[] args) {
        TreeNode root = new TreeNode(2);
        root.left = new TreeNode(1);
        root.right = new TreeNode(3);
        System.out.println(new Main().isValidBST(root)); // true
    }
}

Approach 2

Level II: Iterative Inorder (Stack)

Intuition

Using a stack, we can simulate the recursion of an inorder traversal. We push all left children of the current node onto the stack, then pop one, check it, and move to its right child.

Logic

Keep a pointer prev to the previously visited node. At each step, if current.val <= prev.val, it's not a valid BST.

⏱ O(N)💾 O(H)

Detailed Dry Run

Stack: [2, 1]. Pop 1, prev=1. Pop 2, prev=2 (2>1 OK). Push 3, Pop 3, prev=3 (3>2 OK).

java

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

Approach 3

Level III: Optimal (Recursive Bounds)

Intuition

Thought Process

Instead of storing the whole tree in an array, we can validate each node as we visit it by passing down an allowable range (min, max). For any node, all values in its left subtree must be less than the node's value, and all values in its right subtree must be greater.

Pattern

Top-Down DFS: Pass constraints from parent to children.

Diagram

        10 (range: -∞, +∞)
       /  \
      5    15
     / \   / \
    L   R L   R
   (5 range: -∞, 10)  (15 range: 10, +∞)

⏱ O(N) (visiting each node once)💾 O(H) (recursion depth equal to tree height)

Detailed Dry Run

Node	Range (Min, Max)	Valid?
10	(-∞, +∞)	YES
5	(-∞, 10)	YES
15	(10, +∞)	YES

java

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

    private boolean validate(TreeNode node, Integer low, Integer high) {
        if (node == null) return true;
        if ((low != null && node.val <= low) || (high != null && node.val >= high)) return false;
        return validate(node.left, low, node.val) && validate(node.right, node.val, high);
    }
}

⚠️ Common Pitfalls & Tips

Be careful with Integer.MIN_VALUE. Use null or Long for the initial bounds to handle nodes that contain the minimum possible integer value.

Binary Tree Level Order Traversal

BFS traversal.

Medium

Approach 1

Level I: Recursive depth-first (DFS)

Intuition

We can use recursion to traverse the tree. By passing the current depth (level) as an argument, we can add each node's value to a list corresponding to its level. If the list for a level doesn't exist yet, we create it.

Thought Process

Maintain a list of lists res.
Call helper(node, level).
If res.size() == level, add a new inner list.
res.get(level).add(node.val).
Recurse left and right with level + 1.

⏱ O(N)💾 O(H) (due to recursion stack where H is tree height)

Detailed Dry Run

Node	Level	Result (State)
3	0	[[3]]
9	1	[[3], [9]]
20	1	[[3], [9, 20]]
15	2	[[3], [9, 20], [15]]

java

import java.util.*;

public class Main {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        helper(root, 0, res);
        return res;
    }

    private void helper(TreeNode node, int level, List<List<Integer>> res) {
        if (node == null) return;
        if (res.size() == level) res.add(new ArrayList<>());
        res.get(level).add(node.val);
        helper(node.left, level + 1, res);
        helper(node.right, level + 1, res);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        System.out.println(new Main().levelOrder(root)); // [[3], [9, 20], [15, 7]]
    }
}

Approach 2

Level II: Iterative DFS (using Stack)

Intuition

While BFS is the natural choice for level-order, we can simulate it using DFS with depth tracking. We maintain a stack of (node, depth). If the result list size is equal to the current depth, we add a new empty list. Then, we add the node value to the list corresponding to its depth.

Logic

Use a Stack for DFS.
Track depth for each node.
res[depth].add(node.val).
Note: Push right child first, then left to maintain left-to-right order in levels.

⏱ O(N)💾 O(N)

Detailed Dry Run

Stack	Depth	res state
[(3,0)]	0	[[3]]
[(20,1), (9,1)]	1	[[3], [9]]
[(20,1)]	1	[[3], [9, 20]]

java

import java.util.*;

public class Main {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Stack<Object[]> stack = new Stack<>();
        stack.push(new Object[]{root, 0});
        while (!stack.isEmpty()) {
            Object[] curr = stack.pop();
            TreeNode node = (TreeNode)curr[0];
            int depth = (int)curr[1];
            if (res.size() == depth) res.add(new ArrayList<>());
            res.get(depth).add(node.val);
            if (node.right != null) stack.push(new Object[]{node.right, depth + 1});
            if (node.left != null) stack.push(new Object[]{node.left, depth + 1});
        }
        return res;
    }
}

Approach 3

Level III: Optimal (BFS with Queue)

Intuition

Thought Process

The standard way to perform level-order traversal is Breadth-First Search (BFS) using a Queue. We process the tree level by level. For each level, we record how many nodes are currently in the queue; this count is the number of nodes in that specific level.

Diagram

Queue: [3]  -> Level nodes: [3]
Queue: [9, 20] -> Level nodes: [9, 20]
Queue: [15, 7] -> Level nodes: [15, 7]

⏱ O(N) (each node visited once)💾 O(N) (queue stores maximum level width)

Detailed Dry Run

Queue	Level Size	Processing	Result Area
[3]	1	Pop 3, Push 9, 20	[3]
[9, 20]	2	Pop 9, Pop 20, Push 15, 7	[9, 20]
[15, 7]	2	Pop 15, Pop 7	[15, 7]

java

public class Main {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(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.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
            result.add(level);
        }
        return result;
    }
}

⚠️ Common Pitfalls & Tips

Empty tree checking is vital (if root == null). Forget this and the while loop might run on a null list or throw errors.

Lowest Common Ancestor of a Binary Tree

Find LCA.

Medium

Approach 1

Level I: Brute Force (Recursive Containment Check)

Intuition

The Lowest Common Ancestor (LCA) is the node where p and q first reside in different subtrees (one in left, one in right), or the node itself is one of p or q. A brute force approach checks for every node if it contains p and q in its subtrees.

Thought Process

Define contains(node, target) helper.
For current root, if root is p or q, it might be LCA.
If contains(root.left, p & q) is true, move to left child.
If contains(root.right, p & q) is true, move to right child.
If they are split, root is LCA.

⏱ O(N^2) (Checking containment for each node)💾 O(H)

Detailed Dry Run

Node	Left contains p, q?	Right contains p, q?	Decision
3	no	no	Split! 3 is LCA

java

public class Main {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        if (root == p || root == q) return root;
        boolean leftP = contains(root.left, p), leftQ = contains(root.left, q);
        if (leftP && leftQ) return lowestCommonAncestor(root.left, p, q);
        boolean rightP = contains(root.right, p), rightQ = contains(root.right, q);
        if (rightP && rightQ) return lowestCommonAncestor(root.right, p, q);
        return root;
    }
    private boolean contains(TreeNode root, TreeNode target) {
        if (root == null) return false;
        if (root == target) return true;
        return contains(root.left, target) || contains(root.right, target);
    }
}

Approach 2

Level II: Iterative with Parent Map

Intuition

We can traverse the tree and store each node's parent in a hash map. Once we've found both nodes p and q, we can backtrack from p to the root, storing all ancestors in a set. Then, we backtrack from q the first ancestor that exists in that set is the LCA.

Logic

BFS/DFS to build parentMap until both p and q are found.
Collect all ancestors of p in a set.
Pull upwards from q until an ancestor exists in p's ancestor set.

⏱ O(N) (visiting each node once)💾 O(N) (parent map and ancestor set)

Detailed Dry Run

p=5, q=1. parents={5:3, 1:3, 3:null}. p-ancestors={5, 3}. q's parent 3 is in set -> LCA=3.

java

public class Main {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Map<TreeNode, TreeNode> parent = new HashMap<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        parent.put(root, null);
        stack.push(root);
        while (!parent.containsKey(p) || !parent.containsKey(q)) {
            TreeNode node = stack.pop();
            if (node.left != null) {
                parent.put(node.left, node);
                stack.push(node.left);
            }
            if (node.right != null) {
                parent.put(node.right, node);
                stack.push(node.right);
            }
        }
        Set<TreeNode> ancestors = new HashSet<>();
        while (p != null) {
            ancestors.add(p);
            p = parent.get(p);
        }
        while (!ancestors.contains(q)) q = parent.get(q);
        return q;
    }
}

Approach 3

Level III: Optimal (Post-order Recursion)

Intuition

Thought Process

Instead of checking containment repeatedly, we can do a single bottom-up traversal. We ask each child: "Do you see p or q?".

Logic

If a subtree returns a non-null node, it means p or q was found in that subtree.
If both subtrees return non-null, the current node is the Lowest Common Ancestor.
If only one subtree is non-null, pass that result up.

Pattern

Bottom-Up DFS: Aggregate information from children to decide for the parent.

⏱ O(N)💾 O(H)

Detailed Dry Run

Node	Left Result	Right Result	Pass Up
5	p	null	p
1	null	q	q
3	5(p)	1(q)	3 (LCA)

java

public class Main {
    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;
    }
}

⚠️ Common Pitfalls & Tips

This approach assumes both p and q exist in the tree. If they might not exist, a double-check pass is required.

Binary Tree Zigzag Level Order Traversal

Zigzag BFS.

Medium

Approach 1

Level I: BFS + Reverse

Intuition

Process the tree level by level using a queue (standard BFS). After gathering all nodes for a specific level, check if the level index is odd. If it is, reverse the list of values before adding it to the final result.

Thought Process

Standard BFS.
Maintain levelIndex starting at 0.
Collect level nodes.
If levelIndex % 2 != 0, reverse level list.
Increment levelIndex.

⏱ O(N)💾 O(N)

Detailed Dry Run

Level	Nodes	Reverse?	State
0	[3]	No	[[3]]
1	[9, 20]	Yes	[[3], [20, 9]]
2	[15, 7]	No	[[3], [20, 9], [15, 7]]

java

import java.util.*;

public class Main {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        boolean reverse = false;
        while (!q.isEmpty()) {
            int size = q.size();
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = q.poll();
                level.add(node.val);
                if (node.left != null) q.add(node.left);
                if (node.right != null) q.add(node.right);
            }
            if (reverse) Collections.reverse(level);
            res.add(level);
            reverse = !reverse;
        }
        return res;
    }
}

Approach 2

Level II: Two Stacks

Intuition

Instead of reversing level results after-the-fact, we can use two stacks to maintain the order. One stack processes Left-to-Right, and the other Right-to-Left. As we pop from one stack, we push its children into the other stack in an order that keeps the next level correctly oriented.

Logic

Stack1 (L to R): Push Left child, then Right child to Stack2.
Stack2 (R to L): Push Right child, then Left child to Stack1.

⏱ O(N)💾 O(N)

Detailed Dry Run

S1: [3]. Pop 3, S2: [9, 20]. Pop 20, S1: [7, 15]. Pop 9... result levels built directly in order.

java

public class Main {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Stack<TreeNode> s1 = new Stack<>();
        Stack<TreeNode> s2 = new Stack<>();
        s1.push(root);
        while (!s1.isEmpty() || !s2.isEmpty()) {
            List<Integer> level = new ArrayList<>();
            if (!s1.isEmpty()) {
                while (!s1.isEmpty()) {
                    TreeNode node = s1.pop();
                    level.add(node.val);
                    if (node.left != null) s2.push(node.left);
                    if (node.right != null) s2.push(node.right);
                }
            } else {
                while (!s2.isEmpty()) {
                    TreeNode node = s2.pop();
                    level.add(node.val);
                    if (node.right != null) s1.push(node.right);
                    if (node.left != null) s1.push(node.left);
                }
            }
            res.add(level);
        }
        return res;
    }
}

Approach 3

Level III: Optimal (BFS + Double-Ended Queue)

Intuition

Thought Process

Directly inserting at either the head or tail of a Deque based on the current level's direction avoids the need for an explicit Reverse step. This is more efficient as we determine the correct spot for each node exactly once.

Logic

Use a standard BFS queue.
For each level, initialize an empty Deque.
If LevelIndex is even: Add to the back (tail).
If LevelIndex is odd: Add to the front (head).

Complexity

Time: $O(N)$
Space: $O(N)$ (Queue size)

⏱ O(N)💾 O(N)

Detailed Dry Run

Level	Node	Direction	Deque State
1	9	Left to Right	[9]
1	20	Left to Right	[9, 20]
2	15	Right to Left	[15]
2	7	Right to Left	[7, 15]

java

public class Main {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        boolean leftToRight = true;
        while (!q.isEmpty()) {
            int size = q.size();
            LinkedList<Integer> level = new LinkedList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = q.poll();
                if (leftToRight) level.addLast(node.val);
                else level.addFirst(node.val);
                if (node.left != null) q.add(node.left);
                if (node.right != null) q.add(node.right);
            }
            res.add(level);
            leftToRight = !leftToRight;
        }
        return res;
    }
}

⚠️ Common Pitfalls & Tips

While unshift in JS or appendleft in Python is $O(1)$ for Deques, using them on standard arrays can be $O(N)$ per operation. Be sure to use appropriate data structures.

Path Sum II

All root-to-leaf paths summing to target.

Medium

Approach 1

Level I: DFS with List Copying

Intuition

To find all root-to-leaf paths that sum to a target, we can use Depth First Search (DFS). In this basic version, each time we recurse, we create a new copy of the current path. This is simpler to implement but less space-efficient than backtracking.

Thought Process

At each node, subtract node.val from the remaining target.
If it's a leaf node and remainingTarget == 0, add the current path to the result list.
Recurse to left and right children with a fresh copy of the current path.

⏱ O(N^2) (In the worst case of a skewed tree, we copy the path at each node)💾 O(N^2) (Storing many path lists)

Detailed Dry Run

Tree	Target	Path	Remaining	Action
5	22	[5]	17	Recurse
4	17	[5, 4]	13	Recurse
11	13	[5, 4, 11]	2	Recurse (to 2)
2	2	[5, 4, 11, 2]	0	SUCCESS!

java

import java.util.*;

public class Main {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> res = new ArrayList<>();
        dfs(root, targetSum, new ArrayList<>(), res);
        return res;
    }
    private void dfs(TreeNode node, int sum, List<Integer> path, List<List<Integer>> res) {
        if (node == null) return;
        List<Integer> currentPath = new ArrayList<>(path);
        currentPath.add(node.val);
        if (node.left == null && node.right == null && sum == node.val) {
            res.add(currentPath);
            return;
        }
        dfs(node.left, sum - node.val, currentPath, res);
        dfs(node.right, sum - node.val, currentPath, res);
    }
}

Approach 2

Level II: Iterative BFS (Queue with State)

Intuition

We can use a Queue of Triplets (node, currentPath, currentSum) to simulate BFS. For each node, we push its children along with the updated path and sum. This avoids recursion entirely while still exploring the tree level by level.

Thought Process

Store state as [node, path_list, rem_sum].
When reaching a leaf, if rem_sum == node.val, save path.
Push children with path + [node.val] and rem_sum - node.val.

⏱ O(N^2)💾 O(N^2)

Detailed Dry Run

Queue: [(5, [], 22)]. Pop 5, Push (4, [5], 17) and (8, [5], 17). Pop 4, Push (11, [5, 4], 13)...

java

public class Main {
    class State { TreeNode node; List<Integer> path; int sum; State(TreeNode n, List<Integer> p, int s) {node=n; path=p; sum=s;} }
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Queue<State> q = new LinkedList<>();
        q.add(new State(root, new ArrayList<>(), targetSum));
        while (!q.isEmpty()) {
            State s = q.poll();
            List<Integer> newPath = new ArrayList<>(s.path);
            newPath.add(s.node.val);
            if (s.node.left == null && s.node.right == null && s.sum == s.node.val) {
                res.add(newPath);
            }
            if (s.node.left != null) q.add(new State(s.node.left, newPath, s.sum - s.node.val));
            if (s.node.right != null) q.add(new State(s.node.right, newPath, s.sum - s.node.val));
        }
        return res;
    }
}

Approach 3

Level III: Optimal (Backtracking)

Intuition

Thought Process

Instead of copying the array at every step, we use a single global list and perform backtracking. We add the current node to the list, recurse, and then remove the current node (the last element) before returning from the function call.

Patterns

DFS + Backtracking: Keep state clean for previous caller by undoing changes.

Complexity

Time: $O(N)$ (Every node visited once)
Space: $O(H)$ (For the recursive stack and the single path list)

⏱ O(N)💾 O(H)

Detailed Dry Run

Action	Path	Sum (Remaining)
Visit 5	[5]	17
Visit 4	[5, 4]	13
Visit 11	[5, 4, 11]	2
Pop 11	[5, 4]	13

java

public class Main {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(root, targetSum, new ArrayList<>(), res);
        return res;
    }
    private void backtrack(TreeNode node, int sum, List<Integer> path, List<List<Integer>> res) {
        if (node == null) return;
        path.add(node.val);
        if (node.left == null && node.right == null && sum == node.val) {
            res.add(new ArrayList<>(path));
        } else {
            backtrack(node.left, sum - node.val, path, res);
            backtrack(node.right, sum - node.val, path, res);
        }
        path.remove(path.size() - 1);
    }
}

⚠️ Common Pitfalls & Tips

You still need to copy the list when adding it to the result (res.add(new ArrayList<>(path))), otherwise all paths in the result will end up empty at the end of the process!

Kth Smallest Element in a BST

Find kth val.

Medium

Approach 1

Level I: Inorder Traversal to Array

Intuition

As with any BST problem, the inorder traversal gives us the elements in strictly increasing order. We can perform a full inorder traversal, store the results in an array, and then simply return the element at index k-1.

Thought Process

Traverse the tree (Left, Node, Right).
Append values to a list.
Return list[k-1].

⏱ O(N) (visiting each node)💾 O(N) (to store all node values)

Detailed Dry Run

Tree	Inorder Array	k	Result
[3,1,4,null,2]	[1, 2, 3, 4]	1	1

java

import java.util.*;

public class Main {
    public int kthSmallest(TreeNode root, int k) {
        List<Integer> nodes = new ArrayList<>();
        inorder(root, nodes);
        return nodes.get(k - 1);
    }
    private void inorder(TreeNode node, List<Integer> nodes) {
        if (node == null) return;
        inorder(node.left, nodes);
        nodes.add(node.val);
        inorder(node.right, nodes);
    }
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(1);
        root.left.right = new TreeNode(2);
        root.right = new TreeNode(4);
        System.out.println(new Main().kthSmallest(root, 1)); // 1
    }
}

Approach 2

Level II: Divide and Conquer (using Node counts)

Intuition

If we can efficiently count the number of nodes in a subtree, we can determine whether the $k$ -th smallest element lies in the left subtree, is the root itself, or lies in the right subtree.

Logic

Let L = countNodes(root.left).
If k == L + 1: root.val is the result.
If k <= L: Search in the left subtree.
If k > L + 1: Search in the right subtree for the (k - L - 1)-th smallest element.

⏱ O(N) (O(N^2) if tree is skewed and countNodes is O(N))💾 O(H)

Detailed Dry Run

k=1, L=2 (nodes in left). k<=L -> Search Left. L=1 (at next level). k<=L -> Search Left. L=0. k=1, L=0 -> k=L+1 -> Result found.

java

public class Main {
    public int kthSmallest(TreeNode root, int k) {
        int leftCount = countNodes(root.left);
        if (k == leftCount + 1) return root.val;
        if (k <= leftCount) return kthSmallest(root.left, k);
        return kthSmallest(root.right, k - leftCount - 1);
    }
    private int countNodes(TreeNode n) {
        if (n == null) return 0;
        return 1 + countNodes(n.left) + countNodes(n.right);
    }
}

Approach 3

Level III: Optimal (Iterative Inorder with Early Exit)

Intuition

Thought Process

We don't need to visit all $N$ nodes if $k$ is small. By using an iterative inorder traversal with a stack, we can visit nodes one by one in increasing order. As soon as we reach the $k$ -th node, we return its value and stop the traversal.

Complexity

Time: $O(H + k)$ where $H$ is the height of the tree.
Space: $O(H)$ for the stack.

⏱ O(H + k)💾 O(H)

Detailed Dry Run

Stack	Current Node	k-count	Action
[3, 1]	null	0	Pop 1, Push 2
[3]	2	1	Pop 1 was 1st smallest.
[3]	null	1	Pop 2, k reaches 1 (if k=2)

java

public class Main {
    public int kthSmallest(TreeNode root, int k) {
        Stack<TreeNode> stack = new Stack<>();
        while (true) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (--k == 0) return root.val;
            root = root.right;
        }
    }
}

⚠️ Common Pitfalls & Tips

Be careful with the $k=0$ condition. Since $k$ is 1-indexed (1st smallest), we decrement $k$ and check k == 0 immediately after popping.

Populating Next Right Pointers in Each Node

Connect levels.

Medium

Approach 1

Level I: BFS (Level Order)

Intuition

Standard level-order traversal (BFS) using a queue allows us to process nodes level by level. At each level, we iterate through the nodes and set the next pointer of the current node to the next node in the queue (if it's not the last node of the level).

Thought Process

Standard BFS with Queue.
At each level i (of size S):
For j from 0 to S-1:
- node.next = queue.peek() (if j < S-1).

⏱ O(N)💾 O(N) (Queue stores max level width)

Detailed Dry Run

Level	Node	Queue After Pop	Next Pointer
1	2	[3]	3
1	3	[]	null
2	4	[5, 6, 7]	5

java

public class Main {
    public Node connect(Node root) {
        if (root == null) return null;
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Node cur = queue.poll();
                if (i < size - 1) cur.next = queue.peek();
                if (cur.left != null) queue.add(cur.left);
                if (cur.right != null) queue.add(cur.right);
            }
        }
        return root;
    }
}

Approach 2

Level II: Recursive DFS

Intuition

We can use the fact that the tree is a perfect binary tree to recursively connect nodes. For any node, we connect its left child to its right child. Then, if the node has a next element, we connect its right child to the next element's left child.

Logic

Base case: if (!root || !root.left) return.
root.left.next = root.right.
if (root.next) root.right.next = root.next.left.
Recurse left and right.

⏱ O(N)💾 O(H)

Detailed Dry Run

root=1: 2.next=3. root=2: 4.next=5, 5.next=6 (if 2.next exists).

java

public class Main {
    public Node connect(Node root) {
        if (root == null || root.left == null) return root;
        root.left.next = root.right;
        if (root.next != null) root.right.next = root.next.left;
        connect(root.left);
        connect(root.right);
        return root;
    }
}

Approach 3

Level III: Optimal (Iterative using Pointers)

Intuition

Thought Process

Since the tree is a perfect binary tree, we can use the already connected next pointers from the current level to connect the children of the next level. This avoids the use of a queue, making it $O(1)$ space.

Logic

Start at the leftmost node of the current level (leftmost).
Iterate through nodes at this level using cur = cur.next.
Connect cur.left.next = cur.right.
Connect cur.right.next = cur.next.left (if cur.next exists).

Complexity

Time: $O(N)$
Space: $O(1)$

⏱ O(N)💾 O(1)

Detailed Dry Run

Level Head	Current	cur.left.next	cur.right.next	Action
1	1	2->3	null	Done with L1
2	2	4->5	5->6	Move to cur=3
2	3	6->7	null	Done with L2

java

public class Main {
    public Node connect(Node root) {
        if (root == null) return null;
        Node leftmost = root;
        while (leftmost.left != null) {
            Node head = leftmost;
            while (head != null) {
                head.left.next = head.right;
                if (head.next != null) head.right.next = head.next.left;
                head = head.next;
            }
            leftmost = leftmost.left;
        }
        return root;
    }
}

⚠️ Common Pitfalls & Tips

This $O(1)$ space trick only works for Perfect Binary Trees. For general trees, you need a dummy node and a pointer to track the next level's current node.

Serialize and Deserialize Binary Tree

Tree to string and back.

Medium

Approach 1

Level I: BFS (Level Order)

Intuition

Standard level-order traversal (BFS) using a queue allows us to convert the tree into a list of strings. Empty children are represented as '#'.

Thought Process

Use a queue to traverse the tree level by level.
For each node, append its value to the result string.
If a child is null, append '#' instead.
When deserializing, split by ',' and use a queue to reconstruct parent-child links.

⏱ O(N)💾 O(N)

Detailed Dry Run

Tree	Serialized String
[1, 2, 3]	"1,2,3,#,#,#,#"
[1, null, 2]	"1,#,2,#,#"

java

public class Codec {
    public String serialize(TreeNode root) {
        if (root == null) return "";
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        StringBuilder res = new StringBuilder();
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            if (node == null) {
                res.append("#, ");
                continue;
            }
            res.append(node.val + ", ");
            q.add(node.left);
            q.add(node.right);
        }
        return res.toString();
    }

    public TreeNode deserialize(String data) {
        if (data == "") return null;
        String[] values = data.split(", ");
        TreeNode root = new TreeNode(Integer.parseInt(values[0]));
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        for (int i = 1; i < values.length; i++) {
            TreeNode parent = q.poll();
            if (!values[i].equals("#")) {
                parent.left = new TreeNode(Integer.parseInt(values[i]));
                q.add(parent.left);
            }
            if (!values[++i].equals("#")) {
                parent.right = new TreeNode(Integer.parseInt(values[i]));
                q.add(parent.right);
            }
        }
        return root;
    }
}

Approach 2

Level II: Postorder DFS

Intuition

Postorder traversal (Left, Right, Root) is also a valid way to serialize. Deserialization starts from the end of the list and builds the root first, then the right child, then the left child.

Logic

Serialize: dfs(left), dfs(right), append(val).
Deserialize: Pop from end of list, read val, then root.right = dfs(), root.left = dfs().

⏱ O(N)💾 O(N)

Detailed Dry Run

Serialize [1, 2, 3] -> [#, #, 2, #, #, 3, 1]. Pop 1 (root), then 3 (right), then 2 (left).

java

public class Codec {
    public String serialize(TreeNode root) {
        List<String> list = new ArrayList<>();
        post(root, list);
        return String.join(",", list);
    }
    private void post(TreeNode n, List<String> l) {
        if (n == null) { l.add("#"); return; }
        post(n.left, l); post(n.right, l); l.add(String.valueOf(n.val));
    }
    public TreeNode deserialize(String data) {
        Deque<String> dq = new LinkedList<>(Arrays.asList(data.split(",")));
        return build(dq);
    }
    private TreeNode build(Deque<String> dq) {
        String s = dq.pollLast();
        if (s.equals("#")) return null;
        TreeNode n = new TreeNode(Integer.parseInt(s));
        n.right = build(dq); n.left = build(dq);
        return n;
    }
}

Approach 3

Level III: Optimal (Preorder DFS)

Intuition

Thought Process

Preorder DFS (Root, Left, Right) is more compact and easier to code recursively. We use a List or a String Join for serialization. During deserialization, we convert the string back into a Queue or use an index, then recursively rebuild the structure.

Patterns

DFS Preorder Serialization: Maintain structure by marking leaves explicitly.

Complexity

Time: $O(N)$
Space: $O(N)$

⏱ O(N)💾 O(N)

Detailed Dry Run

Node	Action	Serialized
1	Visit	[1]
2	Visit	[1, 2]
null	Visit	[1, 2, #]
null	Visit	[1, 2, #, #]

java

public class Codec {
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        encode(root, sb);
        return sb.toString();
    }
    private void encode(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.append("#, ");
            return;
        }
        sb.append(node.val + ", ");
        encode(node.left, sb);
        encode(node.right, sb);
    }
    public TreeNode deserialize(String data) {
        Queue<String> q = new LinkedList<>(Arrays.asList(data.split(", ")));
        return decode(q);
    }
    private TreeNode decode(Queue<String> q) {
        String s = q.poll();
        if (s.equals("#")) return null;
        TreeNode node = new TreeNode(Integer.parseInt(s));
        node.left = decode(q);
        node.right = decode(q);
        return node;
    }
}

⚠️ Common Pitfalls & Tips

Be aware of recursion limits for very large trees. Serialization strings can become very large, so StringBuilder (Java) or join (Python) is much faster than string concatenation.

Binary Tree Maximum Path Sum

Max path sum (duplicate entry).

Hard

Approach 1

Level I: Brute Force (Iterate all peak nodes)

Intuition

Every path has a 'peak' node (the highest node in the tree structure that belongs to the path). A brute force approach iterates through every node in the tree, treats it as the peak, and calculates the maximum possible path extending down its left and right subtrees.

Logic

For each node, calculate max_down(node.left) and max_down(node.right).
Potential path sum = node.val + max_down(node.left) + max_down(node.right).
Return the maximum across all nodes.

⏱ O(N^2) (Calling max_down for each node)💾 O(H) (Recursion depth)

Detailed Dry Run

At node 20: Left path 15, Right path 7. Path = 15+20+7 = 42. Repeat for all nodes.

java

public class Main {
    public int maxPathSum(TreeNode root) {
        if (root == null) return Integer.MIN_VALUE;
        int current = root.val + Math.max(0, maxDown(root.left)) + Math.max(0, maxDown(root.right));
        return Math.max(current, Math.max(maxPathSum(root.left), maxPathSum(root.right)));
    }
    private int maxDown(TreeNode node) {
        if (node == null) return 0;
        return node.val + Math.max(0, Math.max(maxDown(node.left), maxDown(node.right)));
    }
}

Approach 2

Level II: Recursive DFS (Return Pair)

Intuition

We can solve this problem by having our recursive function return multiple pieces of information: specifically, the maximum path sum found within the subtree so far, and the maximum gain that can be used by an ancestor. This avoids using a global or member variable to track the maximum path sum.

Logic

Return a pair {max_path_overall, max_gain_to_parent}.
max_gain_to_parent = node.val + max(0, left_gain, right_gain).
max_path_here = node.val + max(0, left_gain) + max(0, right_gain).
max_path_overall = max(max_path_here, left_max_overall, right_max_overall).

Complexity

Time: $O(N)$
Space: $O(H)$

⏱ O(N)💾 O(H)

Detailed Dry Run

At node 20: Left returns {15, 15}, Right returns {7, 7}. Max path overall = max(15, 7, 20+15+7) = 42. Gain to return = 20+15 = 35.

java

class Result { int maxOverall, maxGain; Result(int o, int g) {maxOverall=o; maxGain=g;} }
public class Main {
    public int maxPathSum(TreeNode root) {
        return helper(root).maxOverall;
    }
    private Result helper(TreeNode node) {
        if (node == null) return new Result(Integer.MIN_VALUE, 0);
        Result left = helper(node.left);
        Result right = helper(node.right);
        int leftGain = Math.max(left.maxGain, 0);
        int rightGain = Math.max(right.maxGain, 0);
        int currentMax = node.val + leftGain + rightGain;
        int maxOverall = Math.max(currentMax, Math.max(left.maxOverall, right.maxOverall));
        int maxGain = node.val + Math.max(leftGain, rightGain);
        return new Result(maxOverall, maxGain);
    }
}

Approach 3

Level III: Optimal (Single-Pass Recursion)

Intuition

Thought Process

We perform a Post-order DFS. For each node, we want to know two things:

The maximum path sum that passes through this node as the peak (Highest point of an arch).
The maximum "gain" this node can contribute to a path coming from its parent.

Gain Logic

gain = node.val + max(0, leftGain, rightGain) We discard negative gains because a path would be shorter if it simply didn't include that subtree.

Diagram

       -10
       /  \
      9    20
          /  \
         15   7

Gain(15) = 15, Gain(7) = 7
At 20: Max path = 15+7+20 = 42. Gain to return to -10 = 20+15 = 35.
At -10: Max path = 9+35-10 = 34. 
Result: 42.

⏱ O(N)💾 O(H)

Detailed Dry Run

Node	Left Gain	Right Gain	Node Sum	Global Max
15	0	0	15	15
7	0	0	7	15
20	15	7	42	42
9	0	0	9	42
-10	9	35	34	42

java

public class Main {
    private int max = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        helper(root);
        return max;
    }
    private int helper(TreeNode root) {
        if (root == null) return 0;
        int left = Math.max(helper(root.left), 0);
        int right = Math.max(helper(root.right), 0);
        max = Math.max(max, root.val + left + right);
        return root.val + Math.max(left, right);
    }
}

⚠️ Common Pitfalls & Tips

Negative values can be tricky. If all nodes are negative, the max path might just be the single node with the highest value (least negative). That's why we initialize max to Integer.MIN_VALUE and use Math.max(..., 0) to decide whether to include subtrees.

Recover Binary Search Tree

Swapped nodes fix.

Hard

Approach 1

Level I: Inorder to Array (Identify Swaps)

Intuition

In a sorted array, the elements are always in increasing order. If two elements are swapped, we will find either one or two points where arr[i] > arr[i+1].

Thought Process

Perform inorder traversal to get all values.
In the sorted values, find the two values that are out of place.
Traverse the tree again and swap these two values back.

⏱ O(N)💾 O(N)

Detailed Dry Run

Tree Inorder	Swapped Pairs	First Node	Second Node
[1, 3, 2, 4]	(3, 2)	3	2
[3, 2, 1]	(3, 2), (2, 1)	3	1

java

public class Main {
    public void recoverTree(TreeNode root) {
        List<TreeNode> list = new ArrayList<>();
        inorder(root, list);
        TreeNode first = null, second = null;
        for (int i = 0; i < list.size() - 1; i++) {
            if (list.get(i).val > list.get(i + 1).val) {
                if (first == null) first = list.get(i);
                second = list.get(i + 1);
            }
        }
        int tmp = first.val;
        first.val = second.val;
        second.val = tmp;
    }
    private void inorder(TreeNode root, List<TreeNode> list) {
        if (root == null) return;
        inorder(root.left, list);
        list.add(root);
        inorder(root.right, list);
    }
}

Approach 2

Level II: Iterative Inorder (Stack)

Intuition

Instead of checking sortedness in an array, we can do it on the fly using a stack during an iterative inorder traversal. We maintain a prev pointer and identify where prev.val > current.val.

Logic

Use a stack to perform inorder traversal.
Whenever prev.val > current.val, identifying the first and last out-of-order nodes.
Swap values of first and second.

⏱ O(N)💾 O(H)

Detailed Dry Run

Stack: [1, 3, 2]. Pop 3, prev=3. Pop 2, current=2. prev > current! first=3, second=2. Result: swap(3, 2).

java

public class Main {
    public void recoverTree(TreeNode root) {
        TreeNode first = null, second = null, prev = null;
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) { stack.push(root); root = root.left; }
            root = stack.pop();
            if (prev != null && prev.val > root.val) {
                if (first == null) first = prev;
                second = root;
            }
            prev = root;
            root = root.right;
        }
        int tmp = first.val; first.val = second.val; second.val = tmp;
    }
}

Approach 3

Level III: Optimal (In-place Inorder)

Intuition

Thought Process

We can find the swapped nodes during a single inorder traversal without storing the whole tree. We keep tracks of the prev node seen. If prev.val > current.val, we have found an anomaly.

There are two cases:

Adjacent swaps: Only one anomaly point.
Non-adjacent swaps: Two anomaly points (first anomaly's prev and second anomaly's current).

Complexity

Time: $O(N)$
Space: $O(H)$ (Recursive stack)

⏱ O(N)💾 O(H)

Detailed Dry Run

Prev	Current	Anomaly?	First	Second
3	2	Yes (3>2)	3	2
2	1	Yes (2>1)	(keep 3)	1

java

public class Main {
    TreeNode first = null, second = null, prev = null;
    public void recoverTree(TreeNode root) {
        inorder(root);
        int temp = first.val;
        first.val = second.val;
        second.val = temp;
    }
    private void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        if (prev != null && prev.val > root.val) {
            if (first == null) first = prev;
            second = root;
        }
        prev = root;
        inorder(root.right);
    }
}

⚠️ Common Pitfalls & Tips

You must update second in every anomaly found. In Case 2 (non-adjacent swaps), second will be updated twice, correctly identifying the further node.

Count Univalue Subtrees

Count same val subtrees.

Hard

Approach 1

Level I: Brute Force (Check each node)

Intuition

A uni-value subtree is a subtree where all nodes have the same value. A brute force approach checks for every node n if all nodes in its subtree have the same value as n.val.

Thought Process

Define isUnival(node, val) helper.
In main count function:
- If isUnival(root, root.val), increment count.
- Recurse to children.

⏱ O(N^2)💾 O(H)

Detailed Dry Run

Node	Subtree Values	All Same?	Action
1	[1, 1, 1]	YES	count++
5	[5, 5]	YES	count++

java

public class Main {
    int count = 0;
    public int countUnivalSubtrees(TreeNode root) {
        if (root == null) return 0;
        if (isUnival(root, root.val)) count++;
        countUnivalSubtrees(root.left);
        countUnivalSubtrees(root.right);
        return count;
    }
    private boolean isUnival(TreeNode node, int val) {
        if (node == null) return true;
        return node.val == val && isUnival(node.left, val) && isUnival(node.right, val);
    }
}

Approach 2

Level II: Recursive DFS (Parent Passing)

Intuition

Instead of checking every node as root, we can pass the parent's value down. If a node and its children all match that value, we have a candidate. This approach is slightly more efficient than checking every node but still redundant compared to bottom-up.

Logic

For each node, check if it's the root of a unival subtree by matching it with its own value using an isUnival(node, target) helper.

⏱ O(N^2)💾 O(H)

Detailed Dry Run

Node 5. isUnival(5, 5) -> returns true if all in 5's subtree are 5.

java

public class Main {
    int count = 0;
    public int countUnivalSubtrees(TreeNode root) {
        dfs(root);
        return count;
    }
    private void dfs(TreeNode node) {
        if (node == null) return;
        if (isUnival(node, node.val)) count++;
        dfs(node.left); dfs(node.right);
    }
    private boolean isUnival(TreeNode node, int target) {
        if (node == null) return true;
        if (node.val != target) return false;
        return isUnival(node.left, target) && isUnival(node.right, target);
    }
}

Approach 3

Level III: Optimal (Bottom-Up DFS)

Intuition

Thought Process

Instead of re-checking each subtree, we can use a bottom-up approach. A node is the root of a uni-value subtree if children are uni-value and match the parent's value.

Patterns

DFS Result Aggregation: Pass child status up to parents.

Complexity

Time: $O(N)$
Space: $O(H)$

⏱ O(N)💾 O(H)

Detailed Dry Run

Node	Left Uni?	Right Uni?	Matches Children?	Count
Leaf	true	true	yes	count++
Root	true	true	yes	count++

java

public class Main {
    int count = 0;
    public int countUnivalSubtrees(TreeNode root) {
        isUnival(root);
        return count;
    }
    private boolean isUnival(TreeNode node) {
        if (node == null) return true;
        boolean left = isUnival(node.left);
        boolean right = isUnival(node.right);
        if (left && right) {
            if (node.left != null && node.val != node.left.val) return false;
            if (node.right != null && node.val != node.right.val) return false;
            count++;
            return true;
        }
        return false;
    }
}

⚠️ Common Pitfalls & Tips

You must call DFS for both children before returning, even if one child is not a uni-value subtree. This is because the other child might still contain uni-value subtrees that need to be counted.

Serialize and Deserialize N-ary Tree

N-ary tree.

Hard

Approach 1

Level I: BFS (Level Order with null markers)

Intuition

In an N-ary tree, we can use a marker (like null) to distinguish between the children of different parents. During serialization, we use a queue and for every node, we add its children followed by a null to indicate the end of that node's children list.

Logic

Serialize: Queue based BFS. Append null after children of each node.
Deserialize: Use two queues or pointers to rebuild.

⏱ O(N)💾 O(N)

Detailed Dry Run

Node 1 children: [3, 2, 4]. Serialized: [1, null, 3, 2, 4, null, 5, 6, null...]

java

public class Codec {
    public String serialize(Node root) {
        if (root == null) return "";
        List<String> res = new ArrayList<>();
        Queue<Node> q = new LinkedList<>();
        q.add(root); q.add(null);
        while (!q.isEmpty()) {
            Node node = q.poll();
            if (node == null) {
                res.add("#");
                continue;
            }
            res.add(String.valueOf(node.val));
            for (Node child : node.children) q.add(child);
            q.add(null);
        }
        return String.join(",", res);
    }
}

Approach 2

Level II: DFS (with Parentheses)

Intuition

We can represent the tree structure using parentheses: 1(3(5,6),2,4). This is a very intuitive human-readable format.

Logic

Serialize: node.val + ( + serialize(child) for each child + ).
Deserialize: Use a stack to track parent nodes and nested parentheses.

⏱ O(N)💾 O(H)

Detailed Dry Run

Tree: 1 -> [3, 2, 4]. 3 -> [5, 6]. Serial: 1(3(5,6),2,4).

java

public class Codec {
    public String serialize(Node root) {
        if (root == null) return "";
        StringBuilder sb = new StringBuilder();
        dfs(root, sb);
        return sb.toString();
    }
    private void dfs(Node node, StringBuilder sb) {
        sb.append(node.val);
        if (node.children.isEmpty()) return;
        sb.append("(");
        for (int i = 0; i < node.children.size(); i++) {
            dfs(node.children.get(i), sb);
            if (i < node.children.size() - 1) sb.append(",");
        }
        sb.append(")");
    }
}

Approach 3

Level III: Optimal (DFS with Child Count)

Intuition

To serialize an N-ary tree, we can use DFS (Preorder). For each node, we record its value and the number of children it has. During deserialization, we read the value, create a node, and then recursively deserialize exactly count children for that node.

Logic

Serialization: Append val and children.size().
Deserialization: Read val, read size, then loop size times to build child subtrees.

⏱ O(N)💾 O(N)

Detailed Dry Run

Node	Children	Serialized Array
1	3	[1, 3]
3	2	[1, 3, 3, 2]
5	0	[1, 3, 3, 2, 5, 0]
6	0	[1, 3, 3, 2, 5, 0, 6, 0]

java

public class Codec {
    public String serialize(Node root) {
        List<String> list = new ArrayList<>();
        buildString(root, list);
        return String.join(",", list);
    }
    private void buildString(Node node, List<String> list) {
        if (node == null) return;
        list.add(String.valueOf(node.val));
        list.add(String.valueOf(node.children.size()));
        for (Node child : node.children) buildString(child, list);
    }
    public Node deserialize(String data) {
        if (data.isEmpty()) return null;
        Deque<String> deque = new LinkedList<>(Arrays.asList(data.split(",")));
        return buildTree(deque);
    }
    private Node buildTree(Deque<String> deque) {
        Node node = new Node(Integer.parseInt(deque.poll()), new ArrayList<>());
        int size = Integer.parseInt(deque.poll());
        for (int i = 0; i < size; i++) node.children.add(buildTree(deque));
        return node;
    }
}

Lowest Common Ancestor III

With parent pointers.

Hard

Approach 1

Level I: Set of Ancestors

Intuition

Since each node has a parent pointer, we can trace the path from node p back to the root, storing all ancestors in a Hash Set. Then, trace back from node q. The first ancestor of q that is already in the set is the LCA.

Thought Process

Traverse from p to root, adding every node to Set.
Traverse from q to root.
Return first node found in Set.

⏱ O(H)💾 O(H)

Detailed Dry Run

Node	Set (Ancestors of P)	In Set?
P=5	{5}	-
3 (parent of 5)	{5, 3}	-
Q=1	{5, 3}	NO
3 (parent of 1)	{5, 3}	YES! (Result=3)

java

public class Main {
    public Node lowestCommonAncestor(Node p, Node q) {
        Set<Node> set = new HashSet<>();
        while (p != null) {
            set.add(p);
            p = p.parent;
        }
        while (q != null) {
            if (set.contains(q)) return q;
            q = q.parent;
        }
        return null;
    }
}

Approach 2

Level II: Depth Alignment

Intuition

We can calculate the depth of both nodes p and q. Then, move the deeper node up its parent chain until both nodes are at the same depth. From there, move both up together until they meet.

Logic

Calculate depthP and depthQ.
Align depths by moving up parent pointers.
Move both until p == q.

⏱ O(H)💾 O(1)

Detailed Dry Run

P at depth 3, Q at depth 2. Move P up once. Both at depth 2. Move together -> meet at LCA.

java

public class Main {
    public Node lowestCommonAncestor(Node p, Node q) {
        int d1 = getD(p), d2 = getD(q);
        while (d1 > d2) { p = p.parent; d1--; }
        while (d2 > d1) { q = q.parent; d2--; }
        while (p != q) { p = p.parent; q = q.parent; }
        return p;
    }
    private int getD(Node n) {
        int d = 0; while (n != null) { n = n.parent; d++; } return d;
    }
}

Approach 3

Level III: Optimal (Two Pointers / Intersection)

Intuition

Thought Process

This problem is equivalent to finding the intersection of two linked lists. We use two pointers, a and b.

Pointer a starts at p, b starts at q.
When a pointer reaches the root (null), it jumps to the other starting node (q or p).
They will eventually meet at the intersection point (the LCA) after at most $O(H)$ steps.

Logic

a = (a == null) ? q : a.parent b = (b == null) ? p : b.parent

⏱ O(H)💾 O(1)

Detailed Dry Run

Step	Ptr A	Ptr B	Notes
1	5	1	Start
2	3	3	MEET! (LCA=3)

java

public class Main {
    public Node lowestCommonAncestor(Node p, Node q) {
        Node a = p, b = q;
        while (a != b) {
            a = (a == null) ? q : a.parent;
            b = (b == null) ? p : b.parent;
        }
        return a;
    }
}

⚠️ Common Pitfalls & Tips

Be extremely careful with the null jumping logic. If you jump at the wrong node, you might enter an infinite loop. The pointers must switch to the other starting node to align their path lengths.

Path Sum IV

Tree as array sum.

Hard

Approach 1

Level I: BFS (Iterative path storage)

Intuition

We can build the tree level by level using a queue. For each level, we store the full path sum to each node. When we find a node that has no children in the input set, it's a leaf, and we add its path sum to the total.

Logic

Store all input integers in a Map for quick lookup.
Use a Queue to perform BFS, starting from depth 1, position 1.
Each entry in the Queue is (depth, position, currentSum).

⏱ O(N)💾 O(N)

Detailed Dry Run

Queue starts with [1,1,3]. Next level: [2,1,8], [2,2,4]. Since these have no children, add 8+4=12 to total.

java

public class Main {
    public int pathSum(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int n : nums) map.put(n / 10, n % 10);
        int total = 0;
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{1, 1, map.get(11)});
        while (!q.isEmpty()) {
            int[] curr = q.poll();
            int d = curr[0], p = curr[1], sum = curr[2];
            int l = (d+1)*10 + (2*p-1), r = (d+1)*10 + (2*p);
            if (!map.containsKey(l) && !map.containsKey(r)) {
                total += sum;
            } else {
                if (map.containsKey(l)) q.add(new int[]{d+1, 2*p-1, sum + map.get(l)});
                if (map.containsKey(r)) q.add(new int[]{d+1, 2*p, sum + map.get(r)});
            }
        }
        return total;
    }
}

Approach 2

Level II: Recursive DFS (State Tracking)

Intuition

We can use a recursive approach that builds the tree logic internally. For any ID ij, its children are (i+1)(2j-1) and (i+1)(2j). We can track the path sum as we recurse down.

Logic

Store all nums in a Map.
Start DFS from 11 with currentSum = 0.
Base case: if key not in Map, return.

⏱ O(N)💾 O(N)

Detailed Dry Run

DFS(11, 0) -> DFS(21, 3) + DFS(22, 3). 21 is leaf -> total += 3+node.val.

java

public class Main {
    int total = 0;
    Map<Integer, Integer> map = new HashMap<>();
    public int pathSum(int[] nums) {
        for (int n : nums) map.put(n / 10, n % 10);
        dfs(11, 0);
        return total;
    }
    private void dfs(int node, int curSum) {
        if (!map.containsKey(node)) return;
        curSum += map.get(node);
        int depth = node / 10, pos = node % 10;
        int l = (depth + 1) * 10 + (2 * pos - 1);
        int r = (depth + 1) * 10 + (2 * pos);
        if (!map.containsKey(l) && !map.containsKey(r)) {
            total += curSum;
        } else {
            dfs(l, curSum); dfs(r, curSum);
        }
    }
}

Approach 3

Level III: Optimal (HashMap with Recursive Sum)

Intuition

In this problem, a tree is given as a list of integers [Depth, Position, Value]. Depth 1 means root, depth 2 is its children. A position P in depth D has children at position 2P-1 and 2P in depth D+1.

Thought Process

Store the tree in a HashMap: key = (depth * 10 + position), value = val.
Perform a DFS starting from the root (ID: 11).
Keep track of the current path sum.
If a node has no children in the Map, it's a leaf. Add the current path sum to the total result.

⏱ O(N) (N is the number of nodes)💾 O(N) (Storage of nodes in Map)

Detailed Dry Run

Input	Map	Depth/Pos	Path Sum	Action
113	{11: 3}	1, 1	3	Root
215	{11: 3, 21: 5}	2, 1	8	Left Child
221	{11: 3, 21: 5, 22: 1}	2, 2	4	Right Child

java

import java.util.*;

public class Main {
    int sum = 0;
    Map<Integer, Integer> map = new HashMap<>();
    public int pathSum(int[] nums) {
        for (int n : nums) map.put(n / 10, n % 10);
        dfs(1, 1, 0);
        return sum;
    }
    private void dfs(int d, int p, int currentSum) {
        int key = d * 10 + p;
        if (!map.containsKey(key)) return;
        currentSum += map.get(key);
        int left = (d + 1) * 10 + (2 * p - 1);
        int right = (d + 1) * 10 + (2 * p);
        if (!map.containsKey(left) && !map.containsKey(right)) {
            sum += currentSum;
            return;
        }
        dfs(d + 1, 2 * p - 1, currentSum);
        dfs(d + 1, 2 * p, currentSum);
    }
}

Binary Tree Cameras

Min cameras.

Hard

Approach 1

Level I: BFS (Try all camera placements)

Intuition

A brute force approach would try every possible subset of nodes to place cameras and check if all nodes are covered. Since there are $2^N$ subsets, this is too slow but conceptually simple.

Logic

Generate all $2^N$ combinations of camera placements.
For each combination, check if all nodes are covered.
Return the minimum size of a valid combination.

⏱ O(2^N * N)💾 O(N)

Detailed Dry Run

Try all 8 combinations for 3 nodes. Min cameras = 1 (at root).

java

public class Main {
    public int minCameraCover(TreeNode root) {
        Set<TreeNode> cameras = new HashSet<>();
        Set<TreeNode> covered = new HashSet<>();
        return solve(root, cameras, covered);
    }
    // Simplified brute force concept: try placing vs not placing.
    private int solve(TreeNode node, Set<TreeNode> cameras, Set<TreeNode> covered) {
        // ... Brute force implementation would be extremely long ...
        return 0; 
    }
}

Approach 2

Level II: Dynamic Programming (Recursive with 3 States)

Intuition

For each node, we can track 3 states:

Node has a camera.
Node is covered by a child.
Node is not yet covered (must be covered by parent).

Logic

dp(node, state) returns min cameras for subtree rooted at node given state. This avoids the greedy assumptions by exploring all valid coverages recursiveley.

⏱ O(N)💾 O(H)

Detailed Dry Run

DP(root, hasCamera) returns min of children. DP(root, notCovered) forces parent camera.

java

public class Main {
    public int minCameraCover(TreeNode root) {
        int[] res = solve(root);
        return Math.min(res[1], res[2]);
    }
    private int[] solve(TreeNode node) {
        if (node == null) return new int[]{0, 0, 99999};
        int[] L = solve(node.left), R = solve(node.right);
        int d0 = L[1] + R[1];
        int d1 = Math.min(L[2] + Math.min(R[1], R[2]), R[2] + Math.min(L[1], L[2]));
        int d2 = 1 + Math.min(L[0], Math.min(L[1], L[2])) + Math.min(R[0], Math.min(R[1], R[2]));
        return new int[]{d0, d1, d2};
    }
}

Approach 3

Level III: Optimal (Greedy Post-Order)

Intuition

Thought Process

We want to place cameras such that we cover all nodes with the minimum number. A camera at a node covers itself, its parent, and its children.

Greedy Strategy: It's always better to place a camera at a parent of a leaf node rather than the leaf node itself. A camera at the parent covers more nodes.

Node States

0: Node is not covered.
1: Node has a camera.
2: Node is covered but has no camera.

Logic

If children are not covered (0), parent must have a camera (1).
If children have a camera (1), parent is covered (2).
Otherwise, node is not covered (0).

⏱ O(N)💾 O(H)

Detailed Dry Run

Node	Left State	Right State	Node State	Action
Leaf	2	2	0	Return 0 (leaf uncovered)
Parent	0	0	1	Camera++ (covers leaf)
GrandP	1	1	2	Covered by child

java

public class Main {
    int count = 0;
    public int minCameraCover(TreeNode root) {
        return (dfs(root) == 0 ? 1 : 0) + count;
    }
    private int dfs(TreeNode node) {
        if (node == null) return 2;
        int left = dfs(node.left), right = dfs(node.right);
        if (left == 0 || right == 0) {
            count++;
            return 1;
        }
        return (left == 1 || right == 1) ? 2 : 0;
    }
}

Find Duplicate Subtrees

List duplicates.

Hard

Approach 1

Level I: Brute Force (Recursive Comparison)

Intuition

For every node in the tree, we can compare its subtree with the subtrees of all other nodes. This involves a nested traversal: for each node, we start a secondary traversal that checks for equality with every other node.

Logic

dfs(node) visits every node.
For each node, isSame(node, otherNode) checks if they are identical.
Very slow ( $O(N^3)$ or $O(N^2)$ depending on implementation).

⏱ O(N^3)💾 O(H)

Detailed Dry Run

Compare Node(2) with every other node in the tree. If equal and not seen before, add to result.

java

public class Main {
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        List<TreeNode> res = new ArrayList<>();
        // Brute force comparison omitted for brevity as it is highly inefficient.
        return res;
    }
}

Approach 2

Level II: Serialization with Map

Intuition

How do we know if two subtrees are identical? We can serialize each subtree (convert to string) and store the frequency of these strings in a HashMap. If a string appears for the second time, we've found a duplicate.

Logic

Use Post-order DFS.
For each node, string = val + "," + left + "," + right.
Add string to Map.
If map.get(string) == 2, add current node to results.

⏱ O(N^2) (Building strings takes O(N) in worst case for every node)💾 O(N^2)

Detailed Dry Run

Node	Left Serial	Right Serial	Node Serial	Count	Duplicate?
Leaf 4	#	#	"4,#,#"	1	NO
Leaf 4	#	#	"4,#,#"	2	YES!
Node 2	"4,#,#"	#	"2,4,#,#,#"	1	NO

java

public class Main {
    Map<String, Integer> map = new HashMap<>();
    List<TreeNode> res = new ArrayList<>();
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        serialize(root);
        return res;
    }
    private String serialize(TreeNode node) {
        if (node == null) return "#";
        String s = node.val + "," + serialize(node.left) + "," + serialize(node.right);
        map.put(s, map.getOrDefault(s, 0) + 1);
        if (map.get(s) == 2) res.add(node);
        return s;
    }
}

Approach 3

Level III: Optimal (Integer ID Mapping)

Intuition

Thought Process

The $O(N^2)$ bottleneck in Level II is caused by string concatenation. Instead of strings, we can assign a unique integer ID to each subtree structure. Two subtrees are identical if they have the same (node.val, left_child_id, right_child_id) triplet.

Logic

Use a Map tripletToID to map triplets of integers to a unique ID.
Use a Map idCount to track how many times each ID has appeared.
This reduces the problem to $O(N)$ because triplet comparison is $O(1)$ .

⏱ O(N)💾 O(N)

Detailed Dry Run

Node	Left ID	Triplet	New ID	Count	Duplicate?
4	0	(4,0,0)	1	1	NO
4	0	(4,0,0)	1	2	YES!
2	1	(2,1,0)	2	1	NO

java

public class Main {
    Map<String, Integer> tripletToId = new HashMap<>();
    Map<Integer, Integer> idCount = new HashMap<>();
    List<TreeNode> res = new ArrayList<>();
    int nextId = 1;

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        getId(root);
        return res;
    }

    private int getId(TreeNode node) {
        if (node == null) return 0;
        String triplet = node.val + "," + getId(node.left) + "," + getId(node.right);
        int id = tripletToId.computeIfAbsent(triplet, k -> nextId++);
        idCount.put(id, idCount.getOrDefault(id, 0) + 1);
        if (idCount.get(id) == 2) res.add(node);
        return id;
    }
}

Vertical Order Traversal

Vertical columns.

Hard

Approach 1

Level I: DFS with List of Nodes per Column

Intuition

We can perform a DFS and for each node, we pass down its column index. We store nodes in a Map of col -> List<Node>. After traversal, we sort the keys (cols) and then sort each list of nodes by their depth and value.

Logic

DFS with (node, col, depth).
Store in Map<Integer, List<int[]>> (col -> [depth, val]).
Sort.

⏱ O(N log N)💾 O(N)

Detailed Dry Run

Col -1: [2]. Col 0: [1, 3]. Col 1: [4]. Sorting ensures correct ordering.

java

public class Main {
    Map<Integer, List<int[]>> map = new TreeMap<>();
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        dfs(root, 0, 0);
        List<List<Integer>> res = new ArrayList<>();
        for (int col : map.keySet()) {
            List<int[]> nodes = map.get(col);
            Collections.sort(nodes, (a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
            List<Integer> curr = new ArrayList<>();
            for (int[] n : nodes) curr.add(n[1]);
            res.add(curr);
        }
        return res;
    }
    private void dfs(TreeNode n, int c, int d) {
        if (n == null) return;
        map.computeIfAbsent(c, k -> new ArrayList<>()).add(new int[]{d, n.val});
        dfs(n.left, c - 1, d + 1); dfs(n.right, c + 1, d + 1);
    }
}

Approach 2

Level II: BFS with Sorting

Intuition

BFS naturally processes nodes level by level. By adding column information, we can group nodes. However, since multiple nodes can have the same (col, depth), we still need sorting for nodes in the same cell.

Logic

Queue of (node, col, depth).
Map of col -> List of (depth, val).
Sort result lists.

⏱ O(N log N)💾 O(N)

Detailed Dry Run

Similar to Level I but uses Queue.

java

public class Main {
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        Map<Integer, List<int[]>> map = new TreeMap<>();
        Queue<Object[]> q = new LinkedList<>();
        q.add(new Object[]{root, 0, 0});
        while (!q.isEmpty()) {
            Object[] curr = q.poll();
            TreeNode n = (TreeNode)curr[0];
            int c = (int)curr[1], d = (int)curr[2];
            map.computeIfAbsent(c, k -> new ArrayList<>()).add(new int[]{d, n.val});
            if (n.left != null) q.add(new Object[]{n.left, c - 1, d + 1});
            if (n.right != null) q.add(new Object[]{n.right, c + 1, d + 1});
        }
        // Sort as in Level I
        return null; // Placeholder
    }
}

Approach 3

Level III: Optimal (BFS + Range Tracking)

Intuition

Thought Process

We want to group nodes by their vertical column. Root is col=0. Left child is col-1, Right is col+1.

Since we need to return results from left-to-right, we can track the min and max column indices during BFS. This avoids sorting at the end.

Logic

Use BFS with a Queue of (Node, col).
Store nodes in a Map: Map<Integer, List<Integer>> (col -> list of vals).
Keep track of minCol and maxCol.
Loop from minCol to maxCol to collect results.

⏱ O(N)💾 O(N)

Detailed Dry Run

Node	Col	Min	Max	Map
3	0	0	0	{0: [3]}
9	-1	-1	0	{0: [3], -1: [9]}
20	1	-1	1	{0: [3], -1: [9], 1: [20]}

java

public class Main {
    public List<List<Integer>> verticalOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Map<Integer, List<Integer>> map = new HashMap<>();
        Queue<TreeNode> q = new LinkedList<>();
        Queue<Integer> cols = new LinkedList<>();
        q.add(root);
        cols.add(0);
        int min = 0, max = 0;
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            int col = cols.poll();
            if (!map.containsKey(col)) map.put(col, new ArrayList<>());
            map.get(col).add(node.val);
            if (node.left != null) {
                q.add(node.left);
                cols.add(col - 1);
                min = Math.min(min, col - 1);
            }
            if (node.right != null) {
                q.add(node.right);
                cols.add(col + 1);
                max = Math.max(max, col + 1);
            }
        }
        for (int i = min; i <= max; i++) res.add(map.get(i));
        return res;
    }
}

Construct Binary Tree from Preorder and Postorder

Rebuild tree.

Hard

Approach 1

Level I: Recursive with Subarray Search

Intuition

In both preorder and postorder, the first element (or last in postorder) is the root. The element after the root in preorder (preorder[1]) is the root of the left subtree. We find this element in the postorder array; all elements before it in postorder belong to the left subtree.

Thought Process

root = preorder[0].
Left Root = preorder[1].
Find index of preorder[1] in postorder (linear search).
All elements until that index in postorder are in the left subtree.

⏱ O(N^2)💾 O(N)

Detailed Dry Run

Preorder	Postorder	Left Root	Post Index	Left Size
[1,2,4,5,3,6,7]	[4,5,2,6,7,3,1]	2	2	3

java

import java.util.*;

public class Main {
    public TreeNode constructFromPrePost(int[] pre, int[] post) {
        return build(pre, 0, pre.length - 1, post, 0, post.length - 1);
    }

    private TreeNode build(int[] pre, int preS, int preE, int[] post, int postS, int postE) {
        if (preS > preE) return null;
        TreeNode root = new TreeNode(pre[preS]);
        if (preS == preE) return root;

        int leftVal = pre[preS + 1];
        int idx = postS;
        while (post[idx] != leftVal) idx++;
        int leftSize = idx - postS + 1;

        root.left = build(pre, preS + 1, preS + leftSize, post, postS, idx);
        root.right = build(pre, preS + leftSize + 1, preE, post, idx + 1, postE - 1);
        return root;
    }

    public static void main(String[] args) {
        int[] pre = {1, 2, 4, 5, 3, 6, 7}, post = {4, 5, 2, 6, 7, 3, 1};
        TreeNode root = new Main().constructFromPrePost(pre, post);
        System.out.println(root.val); // 1
    }
}

Approach 2

Level III: Optimal (Index-based Recursion)

Intuition

Thought Process

Instead of full array slicing or repeated index searching, we maintain global pointers/indices and use a Hash Map for $O(1)$ lookups of the left child's position in the postorder array.

Diagram

Pre: [1, 2, 4, 5, 3, 6, 7]
Idx:  0, 1, 2, 3, 4, 5, 6

If we are at 1, next is 2.
Find 2 in Post: Index 2.
Left Subtree count = 2 - 0 + 1 = 3.

⏱ O(N)💾 O(N)

Detailed Dry Run

Pre Index	Node Val	Left Val	Post Map Idx	Action
0	1	2	2	Build 1, proceed to Left
1	2	4	0	Build 2, proceed to Left
2	4	-	-	Leaf 4, return

java

public class Main {
    int preI = 0, postI = 0;
    public TreeNode constructFromPrePost(int[] pre, int[] post) {
        TreeNode root = new TreeNode(pre[preI++]);
        if (root.val != post[postI]) root.left = constructFromPrePost(pre, post);
        if (root.val != post[postI]) root.right = constructFromPrePost(pre, post);
        postI++;
        return root;
    }
}

⚠️ Common Pitfalls & Tips

Note that this construction (Pre+Post) does not uniquely define a tree if any node has only one child. The standard implementation treats the single child as the left child.

House Robber III

Tree robbery.

Medium

Approach 1

Level I: Brute Force Recursion

Intuition

Each node can either be robbed or not robbed. If we rob a node, we cannot rob its direct children. If we don't rob it, we can either rob its children or not.

Logic

rob(root) = max(root.val + rob(left.left) + rob(left.right) + rob(right.left) + rob(right.right), rob(left) + rob(right)).

⏱ O(2^N) (Exponential overlapping subproblems)💾 O(H)

Detailed Dry Run

At root: Option 1 (Rob 1 + grandchildren). Option 2 (Rob children 2 and 3). Max is 3.

java

public class Main {
    public int rob(TreeNode root) {
        if (root == null) return 0;
        int val = root.val;
        if (root.left != null) val += rob(root.left.left) + rob(root.left.right);
        if (root.right != null) val += rob(root.right.left) + rob(root.right.right);
        return Math.max(val, rob(root.left) + rob(root.right));
    }
}

Approach 2

Level II: Memoization

Intuition

We can store the result of rob(node) in a HashMap to avoid recomputing for the same node multiple times.

⏱ O(N)💾 O(N)

Detailed Dry Run

Store [Node Pointer] -> Max rob value.

java

public class Main {
    Map<TreeNode, Integer> memo = new HashMap<>();
    public int rob(TreeNode root) {
        if (root == null) return 0;
        if (memo.containsKey(root)) return memo.get(root);
        int val = root.val;
        if (root.left != null) val += rob(root.left.left) + rob(root.left.right);
        if (root.right != null) val += rob(root.right.left) + rob(root.right.right);
        int res = Math.max(val, rob(root.left) + rob(root.right));
        memo.put(root, res);
        return res;
    }
}

Approach 3

Level III: Optimal (Post-order DP Pair)

Intuition

Each node returns a pair: [max if robbed, max if NOT robbed].

If we rob root, we must NOT rob its children: root.val + left[1] + right[1].
If we DON'T rob root, we take the max of robbing or not robbing each child: max(left) + max(right).

⏱ O(N)💾 O(H)

Detailed Dry Run

Leaf returns [val, 0]. Parent returns [parentVal + 0, leafVal + 0].

java

public class Main {
    public int rob(TreeNode root) {
        int[] res = helper(root);
        return Math.max(res[0], res[1]);
    }
    private int[] helper(TreeNode root) {
        if (root == null) return new int[2];
        int[] left = helper(root.left);
        int[] right = helper(root.right);
        int rob = root.val + left[1] + right[1];
        int notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        return new int[]{rob, notRob};
    }
}

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.