Diameter of an Undirected Tree

Question

The question asks the candidate to determine the diameter of an undirected tree, which is the longest path between any two nodes in the tree.

Codemia · Accepted Answer

To find the diameter of an undirected tree, we can use the following approach:
1. Perform a BFS (or DFS) from an arbitrary node to find the farthest node from it. Let's call this node A.
2. Then, perform another BFS (or DFS) starting from node A to find the farthest node from A, which will be node B. The distance between A and B is the diameter of the tree.

Here is the Python code implementing the above approach:
```python
from collections import deque

def bfs(start_node, graph):
    visited = set()
    queue = deque([(start_node, 0)])  # (node, distance)
    farthest_node = start_node
    max_distance = 0

while queue:
        current_node, current_distance = queue.popleft()
        visited.add(current_node)

if current_distance > max_distance:
            max_distance = current_distance
            farthest_node = current_node

for neighbor in graph[current_node]:
            if neighbor not in visited:
                queue.append((neighbor, current_distance + 1))

return farthest_node, max_distance

def tree_diameter(graph):
    # Step 1: Start from an arbitrary node (0)
    farthest_node_a, _ = bfs(0, graph)
    # Step 2: Start from the farthest node found
    farthest_node_b, diameter = bfs(farthest_node_a, graph)
    return diameter
```
This code uses BFS to find the diameter of the tree.

The time complexity of this algorithm is O(N), where N is the number of nodes in the tree, since each node and edge is processed once during the BFS. The space complexity is also O(N) due to the storage used for the queue and visited nodes.

Consider edge cases such as:
- A tree with only one node, where the diameter should be 0.
- A tree that is a straight line, where the diameter will equal the number of nodes minus one.

Interviewers look for clarity in the explanation of the approach, the ability to write clean and efficient code, and a thorough understanding of time and space complexities. They also appreciate candidates who can anticipate edge cases and discuss potential optimizations.

Diameter of an Undirected Tree

Salesforce

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

Salesforce Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string