Solve binary tree, grid, and heap tasks

Answer the following independent coding tasks:

1. Range sum in a BST: Given the root of a binary search tree and integers low and high, return the sum of all node values v where low <= v <= high. Implement using DFS with BST pruning and analyze time/space complexity.
2. Lowest common ancestor: Given the root of a (not-necessarily-BST) binary tree and two existing nodes p and q, return their lowest common ancestor. Discuss recursive and iterative approaches and their complexities.
3. Minimum round-trip flight cost: You are given two lists—departures = [(date_i, price_i)] and returns = [(date_j, price_j)]. Choose one departure and one return such that return_date > depart_date and the total price is minimized. If the lists are already sorted by date, design an O(n) algorithm; otherwise, describe an O(n log n) approach. Return the chosen pair and the minimal total cost, or indicate no feasible pair.
4. Node equals subtree average: Given a binary tree, count how many nodes have a value equal to the integer average of all values in their subtree (including the node itself), where average is defined as floor(sum / size). Provide an O(n) solution.
5. 0/1 image cluster and border: Given a binary grid (0/
6. and a starting cell (r, c), return all cells that are 4-directionally connected to (r, c) and have the same value as grid[r][c]. Follow-up: return the set of coordinates of all cells that are 4-directional neighbors of this component but are not part of it (the component’s border neighbors). Analyze complexity and discuss BFS vs DFS trade-offs.
7. Validate max-heap binary tree: Given a binary tree, determine whether it is a valid max-heap by checking both completeness (levels filled left to right with no gaps) and the heap-order property (each node’s value >= its children’s values). Implement an O(n) BFS-based check and explain why a naive DFS can fail on completeness.

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?

Range Sum of a BST (DFS with pruning)

You are given a binary search tree encoded as a level-order list tree (using null/None placeholders for missing children), plus integers low and high. Return the sum of all node values v with low <= v <= high.

Use the BST ordering to prune: if a node's value is <= low you never need its left subtree, and if it's >= high you never need its right subtree.

Input format: tree is the level-order array (children skipped when their parent slot is absent). low, high are inclusive bounds.

Output: the integer sum.

Constraints

• 0 <= number of nodes <= 10^4
• Node values and low, high fit in a 32-bit integer
• The tree satisfies the BST property
• low <= high

Examples

Example 1

Input: ([10, 5, 15, 3, 7, None, 18], 7, 15)
Output: 32

Explanation: In-range values are 10, 7, and 15 -> 32. Node 18 and 3 are excluded.

Example 2

Input: ([10, 5, 15, 3, 7, 13, 18, 1, None, 6], 6, 10)
Output: 23

Explanation: In-range values: 10, 7, 6 -> 23.

Hints

1. DFS (stack or recursion) is the natural fit for subtree aggregation.
2. Prune: only recurse left when node.val > low; only recurse right when node.val < high.
3. Add node.val to the running sum exactly when low <= node.val <= high.

Lowest Common Ancestor in a Binary Tree

Given a binary tree encoded as a level-order list tree (with null/None placeholders) and the values p and q of two nodes that exist in the tree, return the value of their lowest common ancestor (LCA).

The tree is not necessarily a BST, so you cannot use ordering shortcuts. Node values are assumed unique for this challenge.

Recursive idea: an LCA is the deepest node that finds p in one subtree and q in the other (or is itself p/q with the other below it).

Constraints

• 2 <= number of nodes <= 10^4
• Node values are unique
• p and q are distinct values that both exist in the tree
• The tree may be arbitrary (not a BST)

Examples

Example 1

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

Explanation: 5 is in the left subtree, 1 in the right; their LCA is the root 3.

Example 2

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

Explanation: 4 is a descendant of 5, so 5 is its own ancestor and the LCA.

Hints

1. Recurse: if a node equals p or q, return it upward.
2. If both the left and right recursive calls return non-null, the current node is the LCA.
3. Otherwise propagate up whichever side found a target.
4. Alternative: BFS to build a child->parent map, walk p's ancestors into a set, then walk q's ancestors until one is in the set.

Minimum Round-Trip Flight Cost

You are given two lists, departures and returns, each a list of [date, price] pairs. Choose exactly one departure and one return such that return_date > depart_date and the total depart_price + return_price is minimized.

Return [depart_date, return_date, total_cost] for the optimal pair, or None/null if no feasible pair exists.

O(n log n) general solution: sort both by date, sweep returns in date order while maintaining the cheapest departure seen with an earlier date. If the inputs are already sorted, the sweep alone is O(n).

Tie-breaking note: when multiple pairs share the minimal total, this reference keeps the cheapest earlier-seen departure (smallest date among equal-price departures) and the earliest qualifying return.

Constraints

• 0 <= len(departures), len(returns) <= 10^5
• dates and prices are non-negative integers
• A valid pair requires return_date strictly greater than depart_date
• Return None/null when no return date is later than any departure date

Examples

Example 1

Input: ([[1, 100], [3, 50], [5, 200]], [[2, 80], [4, 40], [6, 300]])
Output: [3, 4, 90]

Explanation: Depart day 3 ($50) + return day 4 ($40) = $90, the cheapest feasible combination.

Example 2

Input: ([[1, 100]], [[2, 200]])
Output: [1, 2, 300]

Explanation: Only one feasible pair.

Hints

1. Sort departures and returns by date.
2. Sweep returns in increasing date order; before pricing a return, fold in every departure with an earlier date and track the minimum departure price so far.
3. The minimum departure price is monotonic as the return date grows, giving an O(n) sweep after sorting.
4. Guard the infeasible case: if no departure precedes any return, answer is None.

Count Nodes Equal to Subtree Average

Given a binary tree as a level-order list tree (with null/None placeholders), count how many nodes have a value equal to the integer average of all values in that node's subtree, including the node itself. The average is floor(subtree_sum / subtree_size).

A single post-order DFS computes, for each node, the sum and size of its subtree in O(1) from its children's results, giving an overall O(n) solution.

Constraints

• 0 <= number of nodes <= 10^4
• Node values fit in a 32-bit integer (use 64-bit accumulators for subtree sums)
• Average is floor(sum / size)
• Leaf nodes always satisfy the condition (avg of one value is the value)

Examples

Example 1

Input: ([4, 8, 5, 0, 1, None, 6],)
Output: 5

Explanation: Leaves 0, 1, 6 qualify; node 5's subtree {5,6} avg 5; root's subtree sum 24/6 = 4. Node 8's subtree {8,0,1} avg 3 != 8. Total 5.

Example 2

Input: ([1],)
Output: 1

Explanation: Single leaf: average equals its own value.

Hints

1. Post-order DFS: return (sum, size) for each subtree.
2. At each node, sum = left_sum + right_sum + val and size = left_size + right_size + 1.
3. Increment the counter when sum // size == node.val (floor division).
4. Use 64-bit accumulators to avoid overflow on large subtrees in typed languages.

0/1 Image Cluster and Border Neighbors

Given a binary grid grid (cells 0 or 1) and a starting cell (r, c), return the connected component and its border.

Return [component, border] where:

• component = the sorted list of [row, col] cells 4-directionally connected to (r, c) and sharing the value grid[r][c].
• border = the sorted list of in-bounds cells that are 4-directional neighbors of the component but are not part of it.

Both lists are sorted by (row, col). This is a flood-fill (BFS or DFS) plus a neighbor sweep.

Constraints

• 1 <= R, C <= 1000
• Each grid cell is 0 or 1
• 0 <= r < R and 0 <= c < C for a valid start
• Connectivity is 4-directional (up/down/left/right)

Examples

Example 1

Input: ([[1, 1, 0], [1, 0, 0], [0, 0, 1]], 0, 0)
Output: [[[0, 0], [0, 1], [1, 0]], [[0, 2], [1, 1], [2, 0]]]

Explanation: The 1-component is the L-shape at (0,0),(0,1),(1,0); its in-bounds non-component neighbors are (0,2),(1,1),(2,0).

Example 2

Input: ([[1]], 0, 0)
Output: [[[0, 0]], []]

Explanation: Single cell, no neighbors, empty border.

Hints

1. Flood-fill from (r, c), expanding only into neighbors with the same value.
2. Track component membership in a visited set so border detection can test 'not in component'.
3. For the border, scan each component cell's 4 in-bounds neighbors and collect those outside the component (dedup with a set).
4. BFS uses a queue (bounded by frontier width); DFS uses the call stack (risk of overflow on huge components) - both are O(R*C).

Validate a Max-Heap Binary Tree (BFS)

Given a binary tree as a level-order list tree (with null/None placeholders preserving the actual shape), determine whether it is a valid max-heap. Two conditions must both hold:

1. Completeness: every level is fully filled left-to-right, with no internal gaps (a missing child may only be followed by other missing nodes).
2. Heap order: every node's value is >= each of its children's values.

Do a level-order BFS: once you dequeue a missing child (a gap), any later real node violates completeness; check the heap-order property against each present child as you go.

Why naive DFS struggles: a depth-first traversal sees node values and parent-child order fine, but it has no global left-to-right level view, so detecting an internal gap (a hole earlier in a level than a filled slot) requires extra index bookkeeping that BFS gets for free.

Constraints

• 0 <= number of nodes <= 10^4
• An empty tree is treated as a valid (vacuous) max-heap
• Completeness means no real node appears after a missing slot in BFS order
• Heap order compares each node against its present children only

Examples

Example 1

Input: ([9, 7, 8, 3, 6, 2, 1],)
Output: true

Explanation: Complete tree and every parent >= its children.

Example 2

Input: ([9, 7, 8, 3, 6],)
Output: true

Explanation: Last level filled left-to-right with no gaps; heap order holds.

Hints

1. Use BFS and enqueue both children (even null ones) so gaps surface in order.
2. Maintain a 'seen a gap' flag; if you later dequeue a real node after a gap, completeness is violated.
3. For heap order, fail fast if any child's value exceeds its parent's value.
4. An empty tree and a single node are both valid max-heaps.

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

Answer the following independent coding tasks: 1) Range sum in a BST: Given the root of a binary search tree and integers low and high, return the sum of all node values v where low <= v <= high. Implement using DFS with BST pruning and analyze time/space complexity. 2) Lowest common ancestor: Given the root of a (not-necessarily-BST) binary tree and two existing nodes p and q, return their lowest common ancestor. Discuss recursive and iterative approaches and their complexities. 3) Minimum round-trip flight cost: You are given two lists—departures = [(date_i, price_i)] and returns = [(date_j, price_j)]. Choose one departure and one return such that return_date > depart_date and the total pr...

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.