Travelling Salesman (Bitmask DP)

🎯

Travelling Salesman (Bitmask DP)

hardDPGoogleAmazon

Imagine a delivery driver who must visit multiple cities exactly once and return home, trying to minimize the total travel distance.

💡 This problem is a classic example of combinatorial optimization where naive solutions explode exponentially. Beginners struggle because the problem requires considering all permutations of cities, which is factorial in complexity, and understanding how to use bitmasking with dynamic programming to efficiently represent subsets and states.

📋

Problem Statement

Given n cities and a distance matrix dist where dist[i][j] represents the cost to travel from city i to city j, find the minimum cost to start from city 0, visit every city exactly once, and return to city 0.

1 ≤ n ≤ 20dist[i][j] ≥ 0 for all 0 ≤ i, j < ndist[i][i] = 0 for all i

💡

Example

Input"n = 4, dist = [[0,10,15,20],[10,0,35,25],[15,35,0,30],[20,25,30,0]]"

Output80

One optimal path is 0 -> 1 -> 3 -> 2 -> 0 with cost 10 + 25 + 30 + 15 = 80.

• n = 1 → output 0 (only one city, no travel needed)
• All distances zero → output 0 (no cost to travel)
• Asymmetric distances (dist[i][j] != dist[j][i]) → ensure algorithm handles directed costs
• Disconnected graph (some dist[i][j] very large or infinite) → algorithm should still find minimal cost or indicate no solution

🔁

Why DP?

Why greedy fails:

A greedy approach that always picks the nearest unvisited city can fail because it may lead to suboptimal cycles. For example, choosing the closest city first might trap the path into a costly detour later.

DP state:

dp[i][mask] represents the minimum cost to start from city i having already visited the set of cities represented by 'mask'.

Recurrence:dp[i][mask] = min_{j not in mask} (dist[i][j] + dp[j][mask | (1 << j)])

From city i with visited set mask, try going to every unvisited city j and add the cost to get there plus the best cost from j onwards.

⚠️

Common Mistakes

Not using bitmask to represent visited cities

Code becomes inefficient or incorrect due to inability to track visited subsets compactly

✅ Use integer bitmask where each bit represents a city visited or not

Forgetting to return to the start city in the final cost

Output cost is underestimated, failing correctness

✅ Add dist[last_city][0] to the final answer

Not initializing DP table properly (e.g., forgetting to set base case)

DP results are incorrect or infinite, causing wrong answers

✅ Set dp[1][0] = 0 to indicate starting city visited with zero cost

Using recursion without memoization for large n

Exponential time leads to TLE and stack overflow

✅ Add memoization or convert to bottom-up DP

Mixing up mask and city indices in bit operations

Incorrect states accessed, leading to wrong answers or runtime errors

✅ Carefully use (1 << city) and mask & (1 << city) consistently

🧠

Brute Force (Pure Recursion)

💡 This approach is the foundation to understand the problem. It tries all permutations without pruning or caching, which is impractical but essential to grasp the problem's nature.

Intuition

Try every possible order of visiting cities starting from city 0, calculate the total cost for each, and pick the minimum.

Algorithm

1. Start from city 0 with only city 0 visited.
2. Recursively try visiting every unvisited city next.
3. Calculate the cost for each complete path that visits all cities and returns to 0.
4. Return the minimum cost found.

💡 The recursion explores all permutations, which is easy to understand but inefficient.

Recurrence:dp(i, mask) = min_{j not in mask} (dist[i][j] + dp(j, mask | (1 << j)))

</>

Code

def tsp_brute_force(dist):
    n = len(dist)
    ALL_VISITED = (1 << n) - 1

    def dfs(i, mask):
        if mask == ALL_VISITED:
            return dist[i][0]  # return to start
        ans = float('inf')
        for j in range(n):
            if mask & (1 << j) == 0:
                cost = dist[i][j] + dfs(j, mask | (1 << j))
                if cost < ans:
                    ans = cost
        return ans

    return dfs(0, 1)

# Example usage:
if __name__ == '__main__':
    dist = [[0,10,15,20],[10,0,35,25],[15,35,0,30],[20,25,30,0]]
    print(tsp_brute_force(dist))  # Output: 80

Line Notes

def tsp_brute_force(dist):Defines the main function to solve TSP using brute force recursion.

ALL_VISITED = (1 << n) - 1Bitmask representing all cities visited.

if mask == ALL_VISITED:Base case: all cities visited, return cost to go back to start.

for j in range(n):Try all cities to visit next that are not yet visited.

import java.util.*;
public class TSPBruteForce {
    static int n;
    static int[][] dist;
    static int ALL_VISITED;

    static int dfs(int i, int mask) {
        if (mask == ALL_VISITED) return dist[i][0];
        int ans = Integer.MAX_VALUE;
        for (int j = 0; j < n; j++) {
            if ((mask & (1 << j)) == 0) {
                int cost = dist[i][j] + dfs(j, mask | (1 << j));
                if (cost < ans) ans = cost;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        dist = new int[][]{{0,10,15,20},{10,0,35,25},{15,35,0,30},{20,25,30,0}};
        n = dist.length;
        ALL_VISITED = (1 << n) - 1;
        System.out.println(dfs(0, 1)); // Output: 80
    }
}

Line Notes

static int dfs(int i, int mask) {Recursive function to explore all paths from city i with visited mask.

if (mask == ALL_VISITED) return dist[i][0];Base case: all cities visited, return cost to start.

for (int j = 0; j < n; j++) {Try all unvisited cities j to visit next.

int cost = dist[i][j] + dfs(j, mask | (1 << j));Calculate cost of going to city j plus rest of path.

#include <bits/stdc++.h>
using namespace std;

int n;
vector<vector<int>> dist;
int ALL_VISITED;

int dfs(int i, int mask) {
    if (mask == ALL_VISITED) return dist[i][0];
    int ans = INT_MAX;
    for (int j = 0; j < n; j++) {
        if ((mask & (1 << j)) == 0) {
            int cost = dist[i][j] + dfs(j, mask | (1 << j));
            ans = min(ans, cost);
        }
    }
    return ans;
}

int main() {
    dist = {{0,10,15,20},{10,0,35,25},{15,35,0,30},{20,25,30,0}};
    n = (int)dist.size();
    ALL_VISITED = (1 << n) - 1;
    cout << dfs(0, 1) << "\n"; // Output: 80
    return 0;
}

Line Notes

int dfs(int i, int mask) {Recursive function exploring all permutations from city i with visited mask.

if (mask == ALL_VISITED) return dist[i][0];Base case: all cities visited, return cost to start city.

for (int j = 0; j < n; j++) {Try all cities j not visited yet.

int cost = dist[i][j] + dfs(j, mask | (1 << j));Cost to go to city j plus cost of completing tour.

function tspBruteForce(dist) {
  const n = dist.length;
  const ALL_VISITED = (1 << n) - 1;

  function dfs(i, mask) {
    if (mask === ALL_VISITED) return dist[i][0];
    let ans = Infinity;
    for (let j = 0; j < n; j++) {
      if ((mask & (1 << j)) === 0) {
        const cost = dist[i][j] + dfs(j, mask | (1 << j));
        if (cost < ans) ans = cost;
      }
    }
    return ans;
  }

  return dfs(0, 1);
}

// Example usage:
const dist = [[0,10,15,20],[10,0,35,25],[15,35,0,30],[20,25,30,0]];
console.log(tspBruteForce(dist)); // Output: 80

Line Notes

function tspBruteForce(dist) {Main function to solve TSP using brute force recursion.

const ALL_VISITED = (1 << n) - 1;Bitmask representing all cities visited.

if (mask === ALL_VISITED) return dist[i][0];Base case: all cities visited, return cost to start city.

for (let j = 0; j < n; j++) {Try all unvisited cities j to visit next.

⏱

Complexity

TimeO(n!)

SpaceO(n) recursion stack

We try all permutations of n cities, which is factorial time. Space is linear due to recursion depth.

💡 For n=10, this means about 3.6 million permutations, which is too large for practical use.

Interview Verdict: TLE

This approach is too slow for large n but is essential to understand before optimizing.

🧠

Top-Down DP with Memoization (Bitmask DP)

💡 Memoization caches results of subproblems to avoid recomputation, drastically improving efficiency over brute force.

Intuition

Store the minimum cost for each city and visited subset so that repeated states are computed once.

Algorithm

1. Initialize a DP table to store results for each city and visited subset.
2. Recursively compute the minimum cost for each state, returning cached results if available.
3. Try all unvisited cities from the current city and update the DP table.
4. Return the minimum cost starting from city 0 with only city 0 visited.

💡 Memoization avoids repeated work by caching results, making the algorithm feasible for n up to ~20.

Recurrence:dp[i][mask] = min_{j not in mask} (dist[i][j] + dp[j][mask | (1 << j)])

</>

Code

def tsp_memo(dist):
    n = len(dist)
    ALL_VISITED = (1 << n) - 1
    memo = [[-1] * (1 << n) for _ in range(n)]

    def dfs(i, mask):
        if mask == ALL_VISITED:
            return dist[i][0]
        if memo[i][mask] != -1:
            return memo[i][mask]
        ans = float('inf')
        for j in range(n):
            if mask & (1 << j) == 0:
                cost = dist[i][j] + dfs(j, mask | (1 << j))
                if cost < ans:
                    ans = cost
        memo[i][mask] = ans
        return ans

    return dfs(0, 1)

# Example usage:
if __name__ == '__main__':
    dist = [[0,10,15,20],[10,0,35,25],[15,35,0,30],[20,25,30,0]]
    print(tsp_memo(dist))  # Output: 80

Line Notes

memo = [[-1] * (1 << n) for _ in range(n)]Initialize memo table with -1 indicating uncomputed states.

if memo[i][mask] != -1:Return cached result if this state was computed before.

memo[i][mask] = ansStore computed minimum cost for current state.

return dfs(0, 1)Start recursion from city 0 with only city 0 visited.

import java.util.*;
public class TSPMemo {
    static int n;
    static int[][] dist;
    static int ALL_VISITED;
    static int[][] memo;

    static int dfs(int i, int mask) {
        if (mask == ALL_VISITED) return dist[i][0];
        if (memo[i][mask] != -1) return memo[i][mask];
        int ans = Integer.MAX_VALUE;
        for (int j = 0; j < n; j++) {
            if ((mask & (1 << j)) == 0) {
                int cost = dist[i][j] + dfs(j, mask | (1 << j));
                if (cost < ans) ans = cost;
            }
        }
        memo[i][mask] = ans;
        return ans;
    }

    public static void main(String[] args) {
        dist = new int[][]{{0,10,15,20},{10,0,35,25},{15,35,0,30},{20,25,30,0}};
        n = dist.length;
        ALL_VISITED = (1 << n) - 1;
        memo = new int[n][1 << n];
        for (int[] row : memo) Arrays.fill(row, -1);
        System.out.println(dfs(0, 1)); // Output: 80
    }
}

Line Notes

static int[][] memo;Memo table to cache results for states.

if (memo[i][mask] != -1) return memo[i][mask];Return cached result if available.

memo[i][mask] = ans;Store computed minimum cost for current state.

memo = new int[n][1 << n];Initialize memo table with size n x 2^n.

#include <bits/stdc++.h>
using namespace std;

int n;
vector<vector<int>> dist;
int ALL_VISITED;
vector<vector<int>> memo;

int dfs(int i, int mask) {
    if (mask == ALL_VISITED) return dist[i][0];
    if (memo[i][mask] != -1) return memo[i][mask];
    int ans = INT_MAX;
    for (int j = 0; j < n; j++) {
        if ((mask & (1 << j)) == 0) {
            int cost = dist[i][j] + dfs(j, mask | (1 << j));
            ans = min(ans, cost);
        }
    }
    memo[i][mask] = ans;
    return ans;
}

int main() {
    dist = {{0,10,15,20},{10,0,35,25},{15,35,0,30},{20,25,30,0}};
    n = (int)dist.size();
    ALL_VISITED = (1 << n) - 1;
    memo.assign(n, vector<int>(1 << n, -1));
    cout << dfs(0, 1) << "\n"; // Output: 80
    return 0;
}

Line Notes

vector<vector<int>> memo;2D vector to store computed results for states.

if (memo[i][mask] != -1) return memo[i][mask];Return cached result if computed.

memo.assign(n, vector<int>(1 << n, -1));Initialize memo table with -1.

memo[i][mask] = ans;Cache the computed minimum cost.

function tspMemo(dist) {
  const n = dist.length;
  const ALL_VISITED = (1 << n) - 1;
  const memo = Array.from({ length: n }, () => Array(1 << n).fill(-1));

  function dfs(i, mask) {
    if (mask === ALL_VISITED) return dist[i][0];
    if (memo[i][mask] !== -1) return memo[i][mask];
    let ans = Infinity;
    for (let j = 0; j < n; j++) {
      if ((mask & (1 << j)) === 0) {
        const cost = dist[i][j] + dfs(j, mask | (1 << j));
        if (cost < ans) ans = cost;
      }
    }
    memo[i][mask] = ans;
    return ans;
  }

  return dfs(0, 1);
}

// Example usage:
const dist = [[0,10,15,20],[10,0,35,25],[15,35,0,30],[20,25,30,0]];
console.log(tspMemo(dist)); // Output: 80

Line Notes

const memo = Array.from({ length: n }, () => Array(1 << n).fill(-1));Initialize memo table with -1 for all states.

if (memo[i][mask] !== -1) return memo[i][mask];Return cached result if available.

memo[i][mask] = ans;Store computed minimum cost for current state.

return dfs(0, 1);Start recursion from city 0 with only city 0 visited.

⏱

Complexity

TimeO(n^2 * 2^n)

SpaceO(n * 2^n)

Each state (city, visited mask) is computed once, and for each state, we try up to n next cities.

💡 For n=20, this is about 20 * 1,048,576 = 20 million operations, which is feasible with efficient implementation.

Interview Verdict: Accepted

This approach is the standard solution for TSP with up to 20 cities in interviews.

🧠

Bottom-Up DP (Tabulation) with Bitmask

💡 Tabulation builds the DP table iteratively, which can be easier to debug and understand the order of computation.

Intuition

Start from states with fewer visited cities and build up to the full set, computing minimum costs for each city and visited subset.

Algorithm

1. Initialize dp table with infinity except dp[0][1] = 0 (start city visited).
2. Iterate over all subsets of cities (bitmasks).
3. For each city in the subset, try to extend the path by visiting an unvisited city.
4. Update dp for the new subset and city with the minimum cost.
5. Return dp[0][ALL_VISITED] after adding cost to return to start.

💡 This approach ensures all smaller subsets are computed before larger ones, guaranteeing correctness.

Recurrence:dp[mask][i] = min_{j in mask, j != i} (dp[mask ^ (1 << i)][j] + dist[j][i])

</>

Code

def tsp_bottom_up(dist):
    n = len(dist)
    ALL_VISITED = (1 << n) - 1
    dp = [[float('inf')] * n for _ in range(1 << n)]
    dp[1][0] = 0

    for mask in range(1 << n):
        for i in range(n):
            if mask & (1 << i):
                for j in range(n):
                    if mask & (1 << j) and i != j:
                        prev_mask = mask ^ (1 << i)
                        dp[mask][i] = min(dp[mask][i], dp[prev_mask][j] + dist[j][i])

    ans = float('inf')
    for i in range(1, n):
        ans = min(ans, dp[ALL_VISITED][i] + dist[i][0])
    return ans

# Example usage:
if __name__ == '__main__':
    dist = [[0,10,15,20],[10,0,35,25],[15,35,0,30],[20,25,30,0]]
    print(tsp_bottom_up(dist))  # Output: 80

Line Notes

dp = [[float('inf')] * n for _ in range(1 << n)]Initialize DP table with infinity for all states.

dp[1][0] = 0Starting at city 0 with only city 0 visited costs 0.

for mask in range(1 << n):Iterate over all subsets of visited cities.

dp[mask][i] = min(dp[mask][i], dp[prev_mask][j] + dist[j][i])Update dp with minimum cost to reach city i from city j.

import java.util.*;
public class TSPBottomUp {
    public static int tsp(int[][] dist) {
        int n = dist.length;
        int ALL_VISITED = (1 << n) - 1;
        int[][] dp = new int[1 << n][n];
        for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE);
        dp[1][0] = 0;

        for (int mask = 0; mask < (1 << n); mask++) {
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    for (int j = 0; j < n; j++) {
                        if ((mask & (1 << j)) != 0 && i != j && dp[mask ^ (1 << i)][j] != Integer.MAX_VALUE) {
                            dp[mask][i] = Math.min(dp[mask][i], dp[mask ^ (1 << i)][j] + dist[j][i]);
                        }
                    }
                }
            }
        }

        int ans = Integer.MAX_VALUE;
        for (int i = 1; i < n; i++) {
            if (dp[ALL_VISITED][i] != Integer.MAX_VALUE) {
                ans = Math.min(ans, dp[ALL_VISITED][i] + dist[i][0]);
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        int[][] dist = {{0,10,15,20},{10,0,35,25},{15,35,0,30},{20,25,30,0}};
        System.out.println(tsp(dist)); // Output: 80
    }
}

Line Notes

int[][] dp = new int[1 << n][n];DP table for all subsets and current city.

dp[1][0] = 0;Start at city 0 with only city 0 visited.

for (int mask = 0; mask < (1 << n); mask++) {Iterate over all subsets of cities.

dp[mask][i] = Math.min(dp[mask][i], dp[mask ^ (1 << i)][j] + dist[j][i]);Update dp with minimal cost to reach city i.

#include <bits/stdc++.h>
using namespace std;

int tsp(const vector<vector<int>>& dist) {
    int n = (int)dist.size();
    int ALL_VISITED = (1 << n) - 1;
    vector<vector<int>> dp(1 << n, vector<int>(n, INT_MAX));
    dp[1][0] = 0;

    for (int mask = 0; mask < (1 << n); mask++) {
        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) != 0) {
                for (int j = 0; j < n; j++) {
                    if ((mask & (1 << j)) != 0 && i != j && dp[mask ^ (1 << i)][j] != INT_MAX) {
                        dp[mask][i] = min(dp[mask][i], dp[mask ^ (1 << i)][j] + dist[j][i]);
                    }
                }
            }
        }
    }

    int ans = INT_MAX;
    for (int i = 1; i < n; i++) {
        if (dp[ALL_VISITED][i] != INT_MAX) {
            ans = min(ans, dp[ALL_VISITED][i] + dist[i][0]);
        }
    }
    return ans;
}

int main() {
    vector<vector<int>> dist = {{0,10,15,20},{10,0,35,25},{15,35,0,30},{20,25,30,0}};
    cout << tsp(dist) << "\n"; // Output: 80
    return 0;
}

Line Notes

vector<vector<int>> dp(1 << n, vector<int>(n, INT_MAX));Initialize DP table with max int values.

dp[1][0] = 0;Starting at city 0 with only city 0 visited costs 0.

for (int mask = 0; mask < (1 << n); mask++) {Iterate over all subsets of cities.

dp[mask][i] = min(dp[mask][i], dp[mask ^ (1 << i)][j] + dist[j][i]);Update dp with minimal cost to reach city i.

function tspBottomUp(dist) {
  const n = dist.length;
  const ALL_VISITED = (1 << n) - 1;
  const dp = Array.from({ length: 1 << n }, () => Array(n).fill(Infinity));
  dp[1][0] = 0;

  for (let mask = 0; mask < (1 << n); mask++) {
    for (let i = 0; i < n; i++) {
      if ((mask & (1 << i)) !== 0) {
        for (let j = 0; j < n; j++) {
          if ((mask & (1 << j)) !== 0 && i !== j && dp[mask ^ (1 << i)][j] !== Infinity) {
            dp[mask][i] = Math.min(dp[mask][i], dp[mask ^ (1 << i)][j] + dist[j][i]);
          }
        }
      }
    }
  }

  let ans = Infinity;
  for (let i = 1; i < n; i++) {
    if (dp[ALL_VISITED][i] !== Infinity) {
      ans = Math.min(ans, dp[ALL_VISITED][i] + dist[i][0]);
    }
  }
  return ans;
}

// Example usage:
const dist = [[0,10,15,20],[10,0,35,25],[15,35,0,30],[20,25,30,0]];
console.log(tspBottomUp(dist)); // Output: 80

Line Notes

const dp = Array.from({ length: 1 << n }, () => Array(n).fill(Infinity));Initialize DP table with Infinity.

dp[1][0] = 0;Start at city 0 with only city 0 visited.

for (let mask = 0; mask < (1 << n); mask++) {Iterate over all subsets of cities.

dp[mask][i] = Math.min(dp[mask][i], dp[mask ^ (1 << i)][j] + dist[j][i]);Update dp with minimal cost to reach city i.

⏱

Complexity

TimeO(n^2 * 2^n)

SpaceO(n * 2^n)

We fill a DP table of size n * 2^n, and for each state, we try up to n transitions.

💡 This approach is efficient enough for n up to 20 and is often preferred for iterative clarity.

Interview Verdict: Accepted

Bottom-up DP is a robust and interview-friendly approach that avoids recursion overhead.

📊

All Approaches - One-Glance Tradeoffs

💡 Memoization or bottom-up DP are the best choices to implement in interviews for clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n!)	O(n) recursion stack	Yes	No	Mention only - never code
2. Top-Down DP with Memoization	O(n^2 * 2^n)	O(n * 2^n)	Possible but unlikely for n ≤ 20	Yes	Code this for recursive clarity
3. Bottom-Up DP (Tabulation)	O(n^2 * 2^n)	O(n * 2^n)	No	Yes	Code this for iterative clarity and performance

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify the problem and constraints with the interviewer.Explain the brute force approach to show understanding of the problem.Introduce memoization to optimize overlapping subproblems.Present bottom-up DP for iterative clarity and robustness.Discuss time and space complexity and possible optimizations.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

The interviewer tests your understanding of bitmasking, DP state representation, recursion vs iteration, and optimization techniques.

Common Follow-ups

• How to reconstruct the path from DP table → store parent pointers during DP.
• Can we optimize space? → Yes, but tricky due to dependencies.
• What if n > 20? → Use heuristics or approximation algorithms.
• How to handle asymmetric distances? → The same DP works without changes.

💡 These follow-ups test deeper understanding and ability to extend the solution beyond the base problem.

🔍

Pattern Recognition

When to Use

1) Problem involves visiting all nodes exactly once; 2) Costs between nodes given; 3) Need to minimize total cost; 4) Number of nodes small enough for 2^n states.

Signature Phrases

visit every city exactly onceminimum cost to complete the tour

NOT This Pattern When

Problems that require greedy or simple DP without subsets, or those with large n where bitmask DP is infeasible.

Similar Problems

Shortest Hamiltonian Path - similar DP with bitmask but no return to startMinimum Cost Hamiltonian Cycle - classic TSP formulationBitmask DP on Graphs - general technique for subset problems

Practice

1. Consider the following code snippet for computing the diameter of a binary tree. Given the tree: root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3)), what is the final value returned by diameterOfBinaryTree(root)?

easy

A. 5

B. 2

C. 4

D. 3

Solution

1. Step 1: Trace height of left subtree rooted at node 2

   Height of node 4 and 5 is 1 each, so height(2) = 1 + max(1,1) = 2. Diameter updated to max(0,1+1)=2.

2. Step 2: Trace height of right subtree rooted at node 3 and root

   Height(3) = 1 (leaf). At root, diameter = max(2, 2 + 1) = 3. Height(root) = 1 + max(2,1) = 3.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Diameter is edges count on longest path 4->2->1->3 = 3 edges [OK]

Hint: Diameter counts edges, not nodes [OK]

Common Mistakes:

• Returning number of nodes instead of edges
• Off-by-one in height calculation

2. The following code attempts to compute the diameter of a binary tree. Identify the line that contains a subtle bug that causes incorrect results when the longest path does not pass through the root.

medium

A. Line updating diameter: diameter = max(diameter, max(left_height, right_height))

B. Line returning height: return 1 + max(left_height, right_height)

C. Line checking for null node: if not node: return 0

D. Line computing left subtree height: left_height = height(node.left)

Solution

1. Step 1: Understand diameter update logic

   The diameter should be updated with left_height + right_height, representing the longest path through current node.

2. Step 2: Identify incorrect update using max(left_height, right_height)

   Using max(left_height, right_height) only considers one side, missing paths crossing the node, causing incorrect diameter.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Diameter must consider sum of left and right heights, not max of one side [OK]

Hint: Diameter = sum of left and right heights, not max [OK]

Common Mistakes:

• Updating diameter with max of one subtree height
• Forgetting to handle null nodes
• Returning nodes count instead of edges

3. Suppose the problem is modified so that the path can reuse nodes multiple times (i.e., cycles allowed), and the tree is now a general graph with possible cycles. Which of the following approaches correctly adapts the maximum path sum solution to handle this variant?

hard

A. Use the same DP on tree approach with memoization, ignoring cycles since the graph is connected

B. Convert the graph to a tree by removing edges to break cycles, then apply the original DP on tree solution

C. Perform a DFS with cycle detection and use dynamic programming with visited states to avoid infinite loops, tracking maximum sums on simple paths

D. Use a greedy approach to select the highest value nodes repeatedly until no improvement

Solution

1. Step 1: Understand the impact of cycles

   Allowing node reuse and cycles means paths can be infinite unless cycles are detected and handled.

2. Step 2: Identify correct approach

   DFS with cycle detection and DP with visited states prevents infinite loops and correctly computes max sums on simple paths in graphs.

3. Step 3: Why other options fail

   Original DP assumes tree structure; greedy ignores path connectivity; converting graph to tree loses valid paths.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Cycle-aware DFS with DP is necessary for graphs with cycles [OK]

Hint: Cycle detection plus DP needed for graphs with cycles [OK]

Common Mistakes:

• Ignoring cycles causes infinite loops
• Greedy fails on path connectivity
• Tree DP invalid on graphs

4. Suppose the problem is modified so that the binary tree nodes can have negative values, and the diameter is defined as the longest path in terms of number of edges (unchanged). Which modification to the optimal bottom-up DFS algorithm is necessary to correctly compute the diameter?

hard

A. Change the diameter update to consider the sum of node values along the path instead of edge count.

B. Modify the height function to return 0 for negative-valued nodes to avoid decreasing path length.

C. No change needed; the diameter depends only on edges, so negative values do not affect the algorithm.

D. Use a top-down approach to track maximum path sums including negative values.

Solution

1. Step 1: Understand diameter definition depends on edges, not node values

   The diameter is the longest path in terms of edges, so node values (positive or negative) do not affect path length.

2. Step 2: Confirm algorithm only counts edges via heights, so no modification needed

   The existing height and diameter update logic counts edges, so negative values do not require changes.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Diameter counts edges, independent of node values [OK]

Hint: Diameter counts edges, not node values [OK]

Common Mistakes:

• Confusing diameter with max path sum
• Modifying height to exclude negative nodes unnecessarily

5. Suppose the problem changes: now you can reuse elements multiple times to form the longest strictly increasing subsequence. Which modification to the optimized LIS algorithm is correct?

hard

A. The optimized binary search approach cannot be directly adapted; use a DP with memoization considering reuse

B. Modify the DP to consider repeated elements by changing comparison from '>' to '>=' in recursion

C. Use the same binary search approach but allow replacing tails with equal or greater elements (use bisect_right)

D. Sort the array and count the longest consecutive increasing sequence allowing duplicates

Solution

1. Step 1: Understand reuse impact

   Allowing reuse breaks the strictly increasing subsequence definition and the binary search tails logic.

2. Step 2: Evaluate algorithm suitability

   The optimized binary search approach relies on unique progression; reuse requires state tracking, best handled by DP with memoization.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Reuse requires more complex DP, not simple binary search [OK]

Hint: Reuse breaks tails logic; DP with memo needed [OK]

Common Mistakes:

• Trying to fix with bisect_right only
• Changing comparison operators without DP
• Assuming sorting solves reuse problem