Compute waits and find distance-k node pairs

Part 1 — Array next-higher wait: Given an integer array A where A[i] is the measurement for day i (0-indexed), return an array W of the same length such that W[i] is the smallest positive number d where i + d < n and A[i + d] > A[i]. If no such day exists, set W[i] = 0. Aim for an O(n) time solution and justify its correctness and space usage.

Part 2 — Binary tree distance-k pairs: Given a binary tree with unique node values and an integer k ≥ 0, define the distance between two nodes u and v as follows: if one is an ancestor of the other, the distance is the number of intermediate nodes on the path between them; otherwise, it is the sum of their distances to their lowest common ancestor. Return the set of all unordered pairs (u, v), u ≠ v, whose distance equals k. Design an algorithm faster than O(n^ 2), describe the data structures you would use, analyze time and space complexity, and discuss edge cases such as k = 0 or an empty tree.