Find max distance between alive tree nodes

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.

What a Strong Answer Covers

• A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it.
• A correctness argument that explains why the algorithm covers all required cases.
• Time and space complexity, plus at least one alternative approach when relevant.
• Focused tests for normal cases, edge cases, and failure modes.

Follow-up Questions

• How would the approach change if the input were streaming or too large for memory?
• What invariants would you assert in production code?
• Which tests would catch off-by-one, duplicate, or tie-breaking bugs?

Max distance between alive leaf nodes (tree diameter over leaves)

Given a binary tree, the 'alive' nodes are exactly its leaf nodes. Find the maximum distance (number of edges) between any two alive nodes. Since alive nodes are the leaves, this is the tree's leaf-to-leaf diameter.

The tree is given as a LeetCode-style compact level-order array tree, where None marks an absent child of a present node (the first element is the root). Return an integer: the maximum number of edges on a path connecting two leaves. If the tree has fewer than two leaves, return 0.

Provide an O(n) time, O(h) space algorithm (single post-order DFS; h = tree height).

Constraints

• 0 <= number of nodes <= 10^4
• Tree given as a LeetCode-compact level-order array; None marks an absent child of a present node.
• Return 0 when the tree is empty or has fewer than two leaves.
• Distance is measured in edges, not nodes.

Examples

Example 1

Input: ([1, 2, 3, 4, 5, None, 6],)
Output: 4

Explanation: Tree: 1 has children 2,3; 2 has leaves 4,5; 3 has right child 6 (a leaf). Leaves are 4,5,6. Longest leaf path 4->2->1->3->6 = 4 edges.

Example 2

Input: ([1],)
Output: 0

Explanation: Single node is the only leaf; with fewer than two leaves the max distance is 0.

Hints

1. A single post-order DFS suffices. For each node, compute the longest downward path to a leaf in its subtree.
2. At an internal node with two children, a candidate leaf-to-leaf path passes through it: (downDepthLeft + 1) + (downDepthRight + 1). Track the global max of these.
3. A leaf returns downward-depth 0 (itself). Only internal nodes with two non-empty children can form a 'through' path, but the ancestor combination handles single-child chains automatically.

Max distance between alive nodes with arbitrary alive flags

Follow-up: now each node carries an arbitrary boolean 'alive' flag (not necessarily a leaf). Compute the maximum distance (number of edges) between any two alive nodes; intermediate nodes on the connecting path may be alive or not.

The tree is given as a LeetCode-compact level-order array tree (None for absent children of present nodes, root first). The alive argument is a list of booleans, one per non-null node, in the same order this parser assigns node ids (root first, then breadth-first by appearance). Return an integer: the maximum number of edges between two alive nodes, or 0 if fewer than two nodes are alive.

Still O(n) time, O(h) space via a single post-order DFS. (Problem 1 is the special case where the alive set is exactly the leaves.)

Constraints

• 0 <= number of nodes <= 10^4
• alive[k] is the flag for the k-th non-null node in appearance order (root first, breadth-first).
• Intermediate nodes on the connecting path may be alive or not.
• Return 0 when fewer than two nodes are alive.
• Distance is measured in edges.

Examples

Example 1

Input: ([1, 2, 3, 4, 5, None, 6], [False, False, False, True, True, True])
Output: 4

Explanation: Alive = the three leaves (4,5,6). Same as the leaf-diameter case: 4->2->1->3->6 = 4 edges.

Example 2

Input: ([1, 2, 3], [True, True, True])
Output: 2

Explanation: All three alive; farthest pair 2->1->3 = 2 edges.

Hints

1. Same post-order DFS as the leaf case, but the 'reachable target' at each node is now 'nearest alive descendant' (including the node itself if it is alive, at depth 0).
2. For each node collect candidate downward distances to an alive node: dl+1, dr+1, and 0 if the node itself is alive. The two largest of these summed is a path through this node.
3. Return None upward when a subtree contains no alive node, so chains of dead nodes don't spuriously contribute a path.

Solution

Solution Alignment

The prompt asks for an implementation-level answer. The safest way to present it is to define the state, maintain clear invariants, then walk through complexity and tests.

Problem Restatement

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.

Recommended Approach

Choose traversal based on the required view or aggregate. DFS is natural for subtree computations and reconstruction; BFS is natural for level order or side views. Keep per-depth or per-position state when the output depends on columns, rows, or depths.

Correctness

The implementation should maintain an invariant after each loop or operation that directly matches the problem statement. At termination, that invariant implies the returned value has considered every valid candidate exactly once, or has preserved the required data-structure state after every API call.

Complexity

Most tree traversals are O(n) time and O(h) recursion stack for DFS or O(w) queue space for BFS, where h is height and w is maximum width.

Edge Cases and Tests

Empty tree, one node, skewed tree, duplicate values when reconstruction assumes uniqueness, deep recursion, and tie-breaking for same row/column nodes.