Graph vs Tree Key Structural Difference in DSA Typescript - Compare & Choose

Challenge - 5 Problems

🧠 Conceptual

intermediate

Key Structural Difference Between Graph and Tree

Which of the following statements correctly describes the key structural difference between a graph and a tree?

A A tree is a connected graph with no cycles, while a graph can have cycles and may be disconnected.

B A graph always has a root node, but a tree does not have a root.

C A tree can have cycles, but a graph cannot have cycles.

D A graph is always directed, while a tree is always undirected.

💡 Hint

Think about connectivity and cycles in both structures.

A tree is a special type of graph that is connected and has no cycles. Graphs are more general and can have cycles and may be disconnected.

❓ Predict Output

intermediate

Output of Graph vs Tree Edge Count

Given a tree with 5 nodes, what is the number of edges it must have?

DSA Typescript

const nodes = 5;
const edgesInTree = nodes - 1;
console.log(edgesInTree);

A 6

B 4

C 5

D 3

💡 Hint

Remember the formula for edges in a tree.

A tree with n nodes always has n-1 edges.

❓ Predict Output

advanced

Detecting Cycle in Graph Code Output

What is the output of the following TypeScript code that checks for a cycle in an undirected graph?

DSA Typescript

class Graph {
  adjacencyList: Map<number, number[]> = new Map();

  addEdge(u: number, v: number) {
    if (!this.adjacencyList.has(u)) this.adjacencyList.set(u, []);
    if (!this.adjacencyList.has(v)) this.adjacencyList.set(v, []);
    this.adjacencyList.get(u)!.push(v);
    this.adjacencyList.get(v)!.push(u);
  }

  hasCycle(): boolean {
    const visited = new Set<number>();

    const dfs = (node: number, parent: number): boolean => {
      visited.add(node);
      for (const neighbor of this.adjacencyList.get(node) || []) {
        if (!visited.has(neighbor)) {
          if (dfs(neighbor, node)) return true;
        } else if (neighbor !== parent) {
          return true;
        }
      }
      return false;
    };

    for (const node of this.adjacencyList.keys()) {
      if (!visited.has(node)) {
        if (dfs(node, -1)) return true;
      }
    }
    return false;
  }
}

const g = new Graph();
g.addEdge(1, 2);
g.addEdge(2, 3);
g.addEdge(3, 4);
g.addEdge(4, 1);
console.log(g.hasCycle());

A SyntaxError

B false

C undefined

D true

💡 Hint

Check if the edges form a cycle.

The edges form a cycle: 1-2-3-4-1, so the function returns true.

🧠 Conceptual

advanced

Why Trees Cannot Have Cycles

Why is it impossible for a tree to have a cycle?

A Because trees are defined as connected graphs with exactly one path between any two nodes.

B Because trees have multiple paths between nodes.

C Because trees allow cycles only if they are directed.

D Because trees always have disconnected nodes.

💡 Hint

Think about the uniqueness of paths in a tree.

A tree has exactly one path between any two nodes, so cycles are not possible.

❓ Predict Output

expert

Output of Graph Connectivity Check

What is the output of this TypeScript code that checks if an undirected graph is connected?

DSA Typescript

class Graph {
  adjacencyList: Map<number, number[]> = new Map();

  addEdge(u: number, v: number) {
    if (!this.adjacencyList.has(u)) this.adjacencyList.set(u, []);
    if (!this.adjacencyList.has(v)) this.adjacencyList.set(v, []);
    this.adjacencyList.get(u)!.push(v);
    this.adjacencyList.get(v)!.push(u);
  }

  isConnected(): boolean {
    const visited = new Set<number>();
    const nodes = Array.from(this.adjacencyList.keys());
    if (nodes.length === 0) return true;

    const dfs = (node: number) => {
      visited.add(node);
      for (const neighbor of this.adjacencyList.get(node) || []) {
        if (!visited.has(neighbor)) dfs(neighbor);
      }
    };

    dfs(nodes[0]);
    return visited.size === nodes.length;
  }
}

const g = new Graph();
g.addEdge(1, 2);
g.addEdge(2, 3);
g.addEdge(4, 5);
console.log(g.isConnected());

A TypeError

B true

C false

D undefined

💡 Hint

Check if all nodes are reachable from the first node.

The graph has two disconnected parts: 1-2-3 and 4-5, so it is not connected.