DP on Trees Diameter of Tree in DSA C - Time & Space Complexity

Time Complexity: DP on Trees Diameter of Tree

O(n)

Understanding Time Complexity

We want to understand how long it takes to find the longest path in a tree using dynamic programming.

How does the time grow as the tree gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int diameter = 0;

int dfs(int node, int parent, vector<vector<int>>& adj) {
    int max1 = 0, max2 = 0;
    for (int child : adj[node]) {
        if (child == parent) continue;
        int height = dfs(child, node, adj) + 1;
        if (height > max1) {
            max2 = max1;
            max1 = height;
        } else if (height > max2) {
            max2 = height;
        }
    }
    diameter = max(diameter, max1 + max2);
    return max1;
}

// Call dfs(0, -1, adj) to start

This code finds the diameter of a tree by exploring each node and calculating the longest paths down its children.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive depth-first search (DFS) visiting each node once.
• How many times: Each node is visited exactly one time, and each edge is checked once in the adjacency list.

How Execution Grows With Input

As the number of nodes grows, the DFS visits each node and edge once, so the work grows roughly in direct proportion to the number of nodes and edges.

Input Size (n)	Approx. Operations
10	About 10 nodes and 9 edges visited
100	About 100 nodes and 99 edges visited
1000	About 1000 nodes and 999 edges visited

Pattern observation: The operations increase roughly linearly as the tree size increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the diameter grows linearly with the number of nodes in the tree.

Common Mistake

[X] Wrong: "The diameter calculation takes quadratic time because it checks pairs of nodes."

[OK] Correct: The code uses DFS to visit each node once, not checking all pairs separately, so it runs in linear time.

Interview Connect

Understanding this linear time approach shows you can handle tree problems efficiently, a key skill in many coding challenges.

Self-Check

"What if we changed the tree to a graph with cycles? How would the time complexity change?"