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/ 1) 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. 6) 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.