Hi all,
This coding question was asked in the Adobe Online Assessment (Aug 2025) -
The problem revolves around Tree Diameter + Dynamic Programming (Rerooting technique).
📌 Problem Statement (paraphrased)
You are given a tree with n nodes.
A leaf node is defined as a node with degree = 1.
The diameter of a tree is the length of the longest path between any two nodes.
👉 A node is called a special node if:
It is a leaf node, and
It lies at one endpoint of some diameter path.
Your task: Find all special nodes in the tree.
⚡ Key Observations
A tree can have multiple diameter paths, not necessarily unique.
The endpoints of any diameter path are always leaf nodes.
So, our problem reduces to:
Compute the diameter of the tree (length = y).
For each leaf node l, compute the longest path starting from l.
If longest(l) == y, then l is a special node.
🛠️ Step 1: Diameter of Tree
We use Tree DP:
Root the tree at node 1.
Let dp[u] = longest downward path starting from node u.
Transition (Bottom-Up DFS):
dp[u] = 1 + max(dp[child1], dp[child2], …)
This gives the best downward path length from each node.
🛠️ Step 2: Rerooting (Upward DP)
Downward DP alone isn’t enough — we also need to know paths that go upward through the parent.
Define up[u] = longest path starting at u but going upward / outside its own subtree.
For a child c of parent p:
up[c] = max( 1 + up[p], 2 + max(dp[sibling1], dp[sibling2], … excluding c) )
This ensures we consider:
paths going above parent (via ancestors),
paths going sideways into other subtrees.
🖼️ Diagram (Upward DP Transition)
parent(p)
/ |
c1 c2 u
up[u] = max(
1 + up[p], // upward via parent
2 + max(dp[c1], dp[c2], … except u) // via parent + sibling subtree
)
This is the classic rerooting DP trick.
🛠️ Step 3: Identify Special Nodes
Diameter length = y = max(dp[u], up[u]) across all nodes.
For each leaf node l:
If max(dp[l], up[l]) == y, then l is a special node.
✅ Complexity
DFS Downward DP: O(N)
DFS Upward DP (rerooting): O(N)
Checking all leaves: O(N)
Total: O(N), which works for large trees.
Happy DSA Learning :)
