DP on Trees Diameter of Tree in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of diameter calculation on a simple tree

What is the output of the following TypeScript code that calculates the diameter of a tree using DP on trees?

DSA Typescript

type Tree = { [key: number]: number[] };

function treeDiameter(tree: Tree): number {
  let diameter = 0;

  function dfs(node: number, parent: number): number {
    let max1 = 0, max2 = 0;
    for (const child of tree[node] || []) {
      if (child === parent) continue;
      const depth = dfs(child, node);
      if (depth > max1) {
        max2 = max1;
        max1 = depth;
      } else if (depth > max2) {
        max2 = depth;
      }
    }
    diameter = Math.max(diameter, max1 + max2);
    return max1 + 1;
  }

  dfs(0, -1);
  return diameter;
}

const tree = {
  0: [1, 2],
  1: [0, 3, 4],
  2: [0],
  3: [1],
  4: [1]
};

console.log(treeDiameter(tree));

A 2

B 4

C 3

D 5

💡 Hint

Think about the longest path between any two nodes in the tree.

The diameter is the longest path between two nodes. Here, the longest path is from node 3 to node 2 or node 4 to node 2, which has length 3 edges.

🧠 Conceptual

intermediate

Understanding the role of DP in tree diameter calculation

Which statement best describes how dynamic programming (DP) is used in calculating the diameter of a tree?

A DP is used to count the total number of nodes in the tree.

B DP stores the longest path from each node to its descendants to avoid recomputation.

C DP helps in converting the tree into a binary tree for easier diameter calculation.

D DP is used to sort the nodes in the tree before calculating the diameter.

💡 Hint

Think about how repeated calculations are avoided in DFS.

DP stores the longest depths from each node to its children so that these values are reused, avoiding repeated DFS calls.

🔧 Debug

advanced

Identify the error in this diameter calculation code

What error will this TypeScript code produce when calculating the diameter of a tree?

DSA Typescript

type Tree = { [key: number]: number[] };

function treeDiameter(tree: Tree): number {
  let diameter = 0;

  function dfs(node: number, parent: number): number {
    let max1 = 0, max2 = 0;
    for (const child of tree[node] || []) {
      if (child === parent) continue;
      const depth = dfs(child, node);
      if (depth > max1) {
        max2 = max1;
        max1 = depth;
      } else if (depth > max2) {
        max2 = depth;
      }
    }
    diameter = Math.max(diameter, max1 + max2);
    return max1 + 1;
  }

  dfs(0, -1);
  return diameter;
}

const tree = {
  0: [1, 2],
  1: [0, 3, 4]
};

console.log(treeDiameter(tree));

A TypeError because tree[node] can be undefined

B SyntaxError due to missing semicolon

C Runtime error due to infinite recursion

D No error, outputs correct diameter

💡 Hint

Check if all nodes have entries in the tree object.

If a node has no children, tree[node] is undefined, so for-of loop throws TypeError.

🚀 Application

advanced

Calculate diameter for a star-shaped tree

Given a star-shaped tree with 1 center node connected to 5 leaf nodes, what is the diameter of this tree?

A 6

B 5

C 1

D 2

💡 Hint

The diameter is the longest path between two leaves through the center.

The longest path goes from one leaf to another through the center node, which is 2 edges.

❓ Predict Output

expert

Output of diameter calculation on a complex tree

What is the output of this TypeScript code that calculates the diameter of a more complex tree?

DSA Typescript

type Tree = { [key: number]: number[] };

function treeDiameter(tree: Tree): number {
  let diameter = 0;

  function dfs(node: number, parent: number): number {
    let max1 = 0, max2 = 0;
    for (const child of tree[node] || []) {
      if (child === parent) continue;
      const depth = dfs(child, node);
      if (depth > max1) {
        max2 = max1;
        max1 = depth;
      } else if (depth > max2) {
        max2 = depth;
      }
    }
    diameter = Math.max(diameter, max1 + max2);
    return max1 + 1;
  }

  dfs(0, -1);
  return diameter;
}

const tree = {
  0: [1, 2],
  1: [0, 3, 4],
  2: [0, 5],
  3: [1, 6],
  4: [1],
  5: [2, 7, 8],
  6: [3],
  7: [5],
  8: [5]
};

console.log(treeDiameter(tree));

A 6

B 7

C 5

D 8

💡 Hint

Find the longest path between any two nodes in the tree.

The longest path is from node 6 to node 7 or 8, passing through nodes 3,1,0,2,5, length 6 edges.