Find max distance between alive tree nodes
Company: DoorDash
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
Given a binary tree, define alive nodes. Base case: alive nodes are the leaves. Find the maximum distance (number of edges) between any two alive nodes; this is the tree diameter when alive nodes are leaves. Provide an O(n) time, O(h) space algorithm. Follow-ups:
(
1) now each node has a boolean alive flag specified arbitrarily; compute the maximum distance whose endpoints are alive (intermediate nodes may be any).
(
2) support online updates to a node’s alive flag and queries for the current maximum distance.
Quick Answer: This question evaluates a candidate's ability to design and analyze efficient tree algorithms and data structures, focusing on tree traversal, diameter-related reasoning, and meeting specified complexity bounds (O(n) time, O(h) space).