Quick Overview

Find max distance between alive tree nodes evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

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: Find max distance between alive tree nodes evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

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

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

Expected 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.

Input: ([1],)

Expected 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

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

Expected Output: 4

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

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

Expected 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.

Loading coding console...